最短路径算法一

最短路径算法1——Floyed与Dijkstra算法。

Floyed算法：

求图中一个点到另一个点的最短路径，毫无疑问Floyed算法是最简单的，而且是多源最短路径，但时间复杂度很高，达到O(n^3)。

原理就是不断遍历一边所有点，把他们当作中间点，每次更新整个图。

Floyed代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #define N 4200
 4 using namespace std;
 5 int n,m,p,q,a,b,c,dis[N][N];
 6 int main(){
 7     scanf("%d%d%d%d",&n,&m,&p,&q);
 8     for(int i=1;i<=n;++i)
 9         for(int j=1;j<=n;++j)
10             dis[i][j]=4200000;
11     for(int i=1;i<=m;++i){
12         scanf("%d%d%d",&a,&b,&c);
13         dis[a][b]=c;
14         dis[b][a]=c;
15     }
16     for(int k=1;k<=n;++k)
17         for(int i=1;i<=n;++i)
18             for(int j=1;j<=n;++j)
19                 dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
20     printf("%d",dis[p][q]);
21     return 0;
22 }

View Code

Dijkstar算法：

这个算法只能求单源最短路径，时间复杂度为O(n^2)。

蓝点是未确定最短路的点，白点是确定了最短路的点，初始所有点都是蓝点。

原理是先把起点到起点的距离设为0，然后进行n次循环，每次找出没被找过并且到起点距离最短的点，把它从蓝点变为白点，然后枚举所有蓝点，如果可以以此白点为中转点到达枚举到的蓝点的路径更短的话，更新该蓝点最短路径。

该算法可以使用堆优化，给出链接。

Dijkstar代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #define N 42000
 4 using namespace std;
 5 int next[N],to[N],dis[N],num,head[N],n,m,p,q,a,b,c,d[N],minn,u[N],k;
 6 void add(int false_from,int false_to,int false_dis){
 7     next[++num]=head[false_from];
 8     to[num]=false_to;
 9     dis[num]=false_dis;
10     head[false_from]=num;
11 }
12 int main(){
13     scanf("%d%d%d%d",&n,&m,&p,&q);
14     for(int i=1;i<=m;++i){
15         scanf("%d%d%d",&a,&b,&c);
16         add(a,b,c);
17         add(b,a,c);
18     }
19     for(int i=1;i<=n;++i)
20         d[i]=42000000;
21     d[p]=0;
22     for(int i=1;i<=n;++i){
23         minn=42000000;
24         for(int j=1;j<=n;++j)
25             if(!u[j]&&d[j]<minn){
26                 minn=d[j];
27                 k=j;
28             }
29         u[k]=1;
30         for(int j=head[k];j;j=next[j])
31             d[to[j]]=min(d[to[j]],d[k]+dis[j]);
32     }
33     printf("%d",d[q]);
34     return 0;
35 }

View Code