Dijkstra算法和Floyed算法
最短路径：
在非网图中，最短路径是指两顶点之间经历的边数最少的路径。
在网图中，最短路径是指两顶点之间经历的边上权值之和最短的路径。
最短路径问题：
单源点到其他顶点的最短路径：
Dijkstra方法，O（n2）按路径长度递增
任意一对顶点之间的最短路径：
Floyed方法，O（n3）
Dijkstra算法：按路径长度递增
1.设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，
2.对vi∈V-S，假设从源点v到vi的有向边为最短路径（从v到其余顶点的最短路径的初值）。
3.以后每求得一条最短路径v, …, vk，就将vk加入集合S中，并将路径v, …, vk , vi与原来的假设相比较，取路径长度较小者为最短路径。
4.重复上述过程，直到集合V中全部顶点加入到集合S中。
路径长度最短的最短路径（即第一条最短路）的特点：
在这条路径上，必定只含一条边，并且这条边上的权值最小。
下一条路径长度次短的最短路径的特点：
（1）直接从源点到该点(只含一条边)；
（2）从源点经过顶点v1（第一条最短路径所依附的顶点），再到达该顶点(由两条边组成)。
再下一条路径长度次短的最短路径的特点：
（1）直接从源点到该点(只含一条边)；
（2）从源点经过顶点v1，再到达该顶点(由两条边组成)；
（3）从源点经过顶点v2，再到达该顶点（两条条边）；
（4）从源点经过顶点v1、v2，再到达该顶点（多条边）。
其余最短路径的特点：
（1）直接从源点到该点(只含一条边)；
（2）从源点经过已求得最短路径的顶点（集合S中的顶点），再到达该顶点。
迪杰斯特拉算法的主要步骤：
(1) g为用邻接矩阵表示的带权图。
S←{v0} ， dist［i］= g.arcs［v0］［vi］,path[i]=“v0vi”或“”；
将v0到其余顶点的路径长度初始化为权值；
(2) 选择vk，使得
dist［vk］=min(dist［i］ | vi∈V-S)
vk为目前求得的下一条从v0出发的最短路径的终点。
将vk加入到S中
(3) 修改从v0出发到集合V-S上任一顶点vi的最短路径的长度。如果
dist[k]+ g.arcs[k][i]<dist[i]
则将dist[i]修改为
dist[k]+ g.arcs[k][i]
path[i]=path[k]+”vi”
(4) 重复(2)、(3) n-1次，即可按最短路径长度的递增顺序，逐个求出v0到图中其它每个顶点的最短路径。
const int MAX=1000;
void Dijkstra(MGraph g, int v){
for ( i =0; i<g.vexnum ; i++){
dist[i]=g.arcs[v][i];
if ( dist[i]!= MAX)
path [i]=g.vertex[v]+g.vertex[i];
else
path[i]=“”;
}
S[0]=g.vertex[v];
num=1;
While (num<g.vextexNum){
k=0;
for(i=0;i<G.vertexNum;i++)
if((dist[i]<dist[k]) k=i
cout<<dist[k]<<path[k];
s[num++]=G.vertex[k];
for(i=0;i<G.vertexNum;i++)
if(dist[k]+g.arc[k][i]<dist[i] {
dist[i]=dist[k]+g.arc[k][i];
path[i]=path[k]+g.vertex[i];
}
}
}
Floyed算法——基本思想：
设图g用邻接矩阵法表示， 求图g中任意一对顶点vi、 vj间的最短路径。
（-1） 将vi到vj 的最短的路径长度初始化为(vi,vj)， 然后进行如下n次比较和修正：
（0） 在vi、vj间加入顶点v0，比较（vi, v0, vj）和(vi, vj)的路径的长度，取其中较短的路径作为vi到vj的且中间顶点号不大于0的最短路径。
（1） 在vi、vj间加入顶点v1，
得（vi, …，v1）和(v1, …，vj)，其中：
（vi, …, v1）是vi到v1 的且中间顶点号不大于0的最短路径，
(v1, …, vj) 是v1到vj 的且中间顶点号不大于0的最短路径，
这两条路径在上一步中已求出。
将（vi, …, v1, …, vj）与上一步已求出的且vi到vj 中间顶点号不大于0的最短路径比较，取其中较短的路径作为vi到vj 的且中间顶点号不大于1的最短路径。
（2）在vi、vj间加入顶点v2，得
（vi, …, v2）和(v2, …, vj)， 其中：
（vi, …, v2）是vi到v2 的且中间顶点号不大于1的最短路径，
(v2, …, vj) 是v2到vj 的且中间顶点号不大于1的最短路径，
这两条路径在上一步中已求出。
将（vi, …, v2, …, vj）与上一步已求出的且vi到vj 中间顶点号不大于1的最短路径比较， 取其中较短的路径作为vi到vj 的且中间顶点号不大于2的最短路径。
void Floyd(MGraph G)
{
for (i=0; i<G.vertexNum; i++)
for (j=0; j<G.vertexNum; j++)
{
dist[i][j]=G.arc[i][j];
if (dist[i][j]!=∞)
path[i][j]=G.vertex[i]+G.vertex[j];
else path[i][j]="";
}
for (k=0; k<G.vertexNum; k++)
for (i=0; i<G.vertexNum; i++)
for (j=0; j<G.vertexNum; j++)
if (dist[i][k]+dist[k][j]<dist[i][j]) {
dist[i][j]=dist[i][k]+dist[k][j];
path[i][j]=path[i][k]+path[k][j];
}
}
完整代码（Dijkstra）：
/*输入:
5 6
0
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1
或
6 9
0
0 1 1
0 2 12
1 2 9
1 3 3
2 4 5
3 2 4
3 4 13
3 5 15
4 5 4
*/
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
#define N 520
int edge[N][N],weight[N],disp[N];
bool visited[N] = {false};
const int inf = 999999;
int main(){
int prev[N];//用来标注当前结点的上一个结点，以便输出两点间最短路线
fill(edge[0],edge[0] + N * N,inf);//注意这里要是N*N，要不然不是全部
fill(disp,disp + N,inf);
int n,m;//对应城市数，城市之间连线数
cin>>n>>m;
int start_point;
cin>>start_point;//输入起点城市
int a,b,c;
for(int i=0;i < m;i++)
{
cin>>a>>b>>c;
edge[a][b] = edge[b][a] = c;
}
for(int i=0;i<N;i++){
prev[i] = i;//初始状态设每个点的前驱为自身
edge[i][i] = 0;
}
disp[start_point] = 0;
for(int i = 0;i < n;i++){
int u = -1,min = inf;
for(int j = 0;j < n;j++){
if(visited[j] == false && disp[j] <= min)
{
u = j;
min = disp[j];
}
}
if(u == -1)
break;
visited[u] = true;
for(int v = 0;v < n;v++){
if(visited[v] == false && edge[u][v] != inf)
{
if(disp[u] + edge[u][v] < disp[v]){
disp[v] = disp[u] + edge[u][v];
prev[v] = u;//prev保存当前结点的上一个节点，以便输出最短路线
cout<<v<<" "<<prev[v]<<endl;
}
}
}
}
//显示起点到各个点的最短路径
for (int i=0;i<n;i++)
{
cout<<"起点"<<start_point<<"到"<<i<<"的最短距离为: "<<disp[i]<<endl;
}
//显示起到到某个点的线路
int end_point;//终点
cout<<"请输入终点:";
cin>>end_point;
stack<int> myStack;
int temp = end_point;
myStack.push(end_point);//先加终点
while(start_point != temp){
temp = prev[temp];
myStack.push(temp);//注意这里是把当前点的上一个结点放进去，此时换成了temp
}
cout<<"起点"<<start_point<<"到"<<end_point<<"的最短路线为: ";
while(!myStack.empty()){
cout<<myStack.top()<<" ";
myStack.pop();
}
return 0;
}
完整代码（Floyed）：
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
const int MaxSize=100;
class MGraph
{
public:
MGraph(char a[],int n,int e);
~MGraph(){}
friend void Floyd(MGraph G);
private:
char vertex[MaxSize]; //节点数组
int arc[MaxSize][MaxSize]; //矩阵
int vertexNum,arcNum; //节点数与边数
int visited[MaxSize]; //访问记录
};
MGraph::MGraph(char a[],int n,int e)
{
int i,j,k;
vertexNum=n;
arcNum=e;
for(i=0;i<vertexNum;i++)
{
vertex[i]=a[i];
}
for(i=0;i<vertexNum;i++)
for(j=0;j<vertexNum;j++)
{
arc[i][j]=0;
}
for(int p=0;p<arcNum;p++)
{
std::cout<<"输入第"<<p+1<<"条边及权值："<<std::endl;
std::cin>>i>>j>>k;
arc[i][j]=k;
}
}
void Floyd(MGraph G)
{
int i,j,k;
int dist[MaxSize][MaxSize]={0};
for(i=0;i<G.vertexNum;i++) //初始化最短路径数组，使两点间路径初始为直接权值
for(j=0;j<G.vertexNum;j++)
{
dist[i][j]=G.arc[i][j];
}
for(k=0;k<G.vertexNum;k++)
for(j=0;j<G.vertexNum;j++)
for(i=0;i<G.vertexNum;i++)
if((dist[i][k]+dist[k][j]<dist[i][j]&&dist[i][k]!=0&&dist[k][j]!=0&&dist[i][j]!=0)||dist[i][j]==0)
{
dist[i][j]=dist[i][k]+dist[k][j];
}
for(i=0;i<G.vertexNum;i++)
for(j=0;j<G.vertexNum;j++)
if(i!=j)
{
std::cout<<G.vertex[i]<<"到"<<G.vertex[j]<<"的最短路径为："<<dist[i][j]<<std::endl;
}
}
int main()
{
int e,n;
std::cout<<"点的个数："<<" ";
std::cin>>e;
std::cout<<"边的个数："<<" ";
std::cin>>n;
char s[e];
for(int i=0;i<e;i++)
{
std::cout<<"输入第"<<i+1<<"个点：";
std::cin>>s[i];
}
MGraph m(s,e,n);
Floyd(m);
return 0;
}
一起加油！学好数据结构和算法！！！
今天的文章Dijkstra算法和Floyed算法分享到此就结束了，感谢您的阅读。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/5709.html
