单源最短路径—Dijkstra算法

单源最短路径

单源最短路径问题（Single Source Shortest Path， SSSP问题）是说，给定一张有向图G=(V,E)，V是点集，E是边集，|V|=n，|E|=m，节点以[1,n]之间的连续整数编号，(x, y, z)描述从x出发，到达y，长度为z的有向边。

Dijkstra算法

初始化d[起点] = 0，其余的点为正无穷。
找出一个未被标记，d[x]最小的点
标记，扫描所有出边，若找到更小的，则用其更新。
重复2、3，直到所有点被标记。

邻接矩阵：

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 const int SIZE = 3010;
 5 int a[SIZE][SIZE], d[SIZE], m, n;
 6 bool v[SIZE];
 7 
 8 void dijkstra(){
 9     memset( d, 0x3f, sizeof d );
10     memset( v, 0, sizeof v );
11     d[1] = 0;
12     for( int i = 1; i < n; i++ ){
13         int x = 0;
14         for( int j = 1; j <= n; j++ )
15             if( !v[j] && ( x == 0 || d[j] < d[x] ) ) x = j;
16         v[x] = 1;
17         for( int y = 1; y < n; y++ )
18             d[y] = min( d[y], d[x] + a[x][y] );        
19     }
20 }
21 int main(){
22     cin >> n >> m;
23     memset( a, 0x3f, sizeof a );
24     for( int i = 1; i <= n; i++ ) a[i][i] = 0;
25     for( int i = 1; i <= m; i++ ){
26         int x, y, z;
27         cin >> x >> y >> z;
28         a[x][y] = min( a[x][y], z );
29     }
30     dijkstra();
31     for( int i = 1; i <= n; i++ ){
32         cout << d[i] <<"
";
33     }
34     
35     return 0;
36 }

链式前向星：

 1 #include<iostream>
 2 #include<queue>
 3 #include<cstring>
 4 #include<cstdio>
 5 using namespace std;
 6 const int N = 100010, M = 1000010;
 7 int head[N], ver[N], Next[N], edge[N], d[N];
 8 bool v[N];
 9 int m, n, tot;
10 priority_queue< pair<int, int> > q;
11 void add(int x, int y, int z){
12     ver[++tot] = y, edge[tot] = z;
13     Next[tot] = head[x], head[x] = tot;
14 }
15 void dijkstra(){
16     memset(d, 0x3f, sizeof d);
17     memset(v, 0, sizeof v);
18     d[1] = 0;
19     q.push(make_pair(0, 1));
20     while(q.size()){
21         int x = q.top().second; q.pop();
22         if(v[x]) continue;
23         v[x] = 1;
24         for(int i=head[x]; i; i=Next[i]){
25             int y = ver[i], z = edge[i];
26             if(d[y] > d[x] + z){
27                 d[y] = d[x] + z;
28                 q.push(make_pair(-d[y], y));
29             }
30         }
31     }
32 }
33 int main(){
34     cin >> n >> m;
35     for(int i=1; i<=m; i++){
36         int x, y, z;
37         cin >> x >> y >> z;
38         add(x, y, z);
39     }
40     dijkstra();
41     for(int i=1; i<=n; i++){
42         cout << d[i] <<"
";
43     }    
44     return 0;
45 }