最短路径

一、单源最短路径

Dijkstra算法

1.该算法常用于求在一个带权有向图中某个顶点到其余顶点的最短路径。该算法的实现可以用一句话说明：先求出长度离源点最短的一条路径，再参照该最短路径求出长度次短的一条路径，直到求出从源点到其他各个顶点的最短路径。

2.Dijkstra算法的基本思想：先根据是否已经求的最短路径将顶点分成两个集合S和V-S(V是顶点的总集合)，初始时集合S中只有源点u ，然后后续从V-S中剔除加到集合S的顶点是已经确定了到集合S中的最短路径的顶点。

3.算法实现：

 1.先根据输入的边和顶点构建一个邻接矩阵（map[u][v]=w:从u到v的路径长度为w），不能互相到达的两个顶点赋一个很大的值。

2.输入起始点u，初始化dis数组，记住点u到每一点i的初始距离，注意dis[u]=0因为自己到自己为0。用flag数组来记录判断每个点是否已经加入最优路径点的集合。

3.在剩下的V-S集合中寻找一个和S中元素相连的最小顶点，然后将它加入S集合中，再以这个点进行边松弛更新dis数组中的值。

4.循环第3步n-1次，得到答案。

5.该算法的时间复杂度为O（n*n）。

 4.代码如下：

#include"stdio.h"
#define N 100
#define INF 999999
int map[N][N],dist[N],p[N],n,m;
int flag[N];
void djk(int u)
{int i,j;	for(i=1;i<=n;i++){dist[i]=map[u][i];//初始化源点到其他点的距离printf("%d ",dist[i]);flag[i]=0; //    if(dist[i]==INF)//与源点不连通//	p[i]=-1;//	else p[i]=u;//顶点i到源点u有边相连，设置前驱数组为u }flag[u]=1;//初始化已经选择了最优路径的集合，只有一个元素：udist[u]=0;//自己到自己的最短路径为0	for(i=1;i<=n;i++){ 	int tmp=INF,t=u;for(j=1;j<=n;j++)//在已经找到最优路径的周围寻找与最优路径相连的最短路径（还未被选入） {if(!flag[j]&&dist[j]<tmp){t=j;tmp=dist[j];} }	//if(t==u) return; //未找到t退出循环 flag[t]=1;//将t加入最优路径的队伍for(j=1;j<=n;j++)//更新未加入最优路径到最优路径的距离 {if(!flag[j]&&map[t][j]<INF){if(dist[j]>(dist[t]+map[t][j]))//经过t到达j的路径更短 {dist[j]=dist[t]+map[t][j];				//	p[j]=t;//记录j的前驱为t }			} }u=t; 
} 
} 
main()
{int u,v,w,st;int i,j;scanf("%d %d",&n,&m);//城市个数，路线个数for(i=1;i<=n;i++)//初始化图的邻接矩阵for(j=1;j<=n;j++){	map[i][j]=INF;	} while(m--){scanf("%d %d %d",&u,&v,&w);map[u][v]=w;}for(i=1;i<=n;i++)//初始化图的邻接矩阵{for(j=1;j<=n;j++)printf("%d    ",map[i][j]);printf("\\n");}
}

二、多源最短路径

Floyd算法

1.该算法用于求一对顶点之间的最短路径，在这个算法中，我们将每两个顶点的最短路径直接存储在map数组中。

2.该算法的基本思想很简单：查看两点之间的距离是否可以通过从其他点在中间进行中转而达到实现两点的距离更小。

算法实现：

1.构建邻接矩阵。

2.对于每两个点都判断一下是否可以通过某些点从中中转达到距离更短。

3.该算法要用到三个for循环，时间复杂度为O（n*n*n）。

3.代码如下：

#include"stdio.h"
int map[100][100],n,m;
int inf=999999;
main()
{int i,j,k,s,e;int u,v,w;scanf("%d %d",&n,&m);//输入顶点和边 scanf("%d %d",&s,&e);//输入要查询的2起点和终点 for(i=1;i<=n;i++)//初始化图 {for(j=1;j<=n;j++)if(i==j) map[i][j]=0;else map[i][j]=inf;}for(i=1;i<=m;i++)//输入边和边权 {scanf("%d %d %d",&u,&v,&w);map[u][v]=w;}for(k=1;k<=n;k++)//边松弛 {for(i=1;i<=n;i++){for(j=1;j<=n;j++)if(map[i][j]>map[i][k]+map[k][j])map[i][j]=map[i][k]+map[k][j];}}for(i=1;i<=n;i++)//输出所有的最优路径 {for(j=1;j<=n;j++)printf("%d ",map[i][j]);printf("\\n");}printf("%d",map[s][e]);//查询路径长度 
}

 三、Dijkstra算法和Floyd算法的区别

1.Floyd算法是求任意两点之间的距离，是多源最短路径，而Dijkstra算法是求一个顶点到其他顶点的最短路径，是单源最短路径。

2.Floyd算法属于动态规划，我们在写核心代码时候就是相当于推dp状态方程，Dijkstra(迪杰斯特拉)算法属于贪心算法。

3.Dijkstra(迪杰斯特拉)算法时间复杂度一般是 O ( n 2 ) O(n^2)O(n2) ,Floyd算法时间复杂度是 O ( n 3 ) O(n^3)O(n3),Dijkstra(迪杰斯特拉)算法比Floyd算法块。

4.Floyd算法可以算带负权的，而Dijkstra(迪杰斯特拉)算法是不可以算带负权的。