最短路径（迪杰斯特拉算法）

求上图中从V1 到V10的最短路径

程序输入说明

输入图的邻接矩阵表示

程序输出说明

输出路径序列

程序输入样例

0 2 5 1 -1 -1 -1 -1 -1 -1
-1 0 -1 -1 12 14 -1 -1 -1 -1
-1 -1 0 -1 6 10 4 -1 -1 -1
-1 -1 -1 0 13 12 11 -1 -1 -1
-1 -1 -1 -1 0 -1 -1 3 9 -1
-1 -1 -1 -1 -1 0 -1 6 5 -1
-1 -1 -1 -1 -1 -1 0 -1 10 -1
-1 -1 -1 -1 -1 -1 -1 0 -1 5
-1 -1 -1 -1 -1 -1 -1 -1 0 2
-1 -1 -1 -1 -1 -1 -1 -1 -1 0

程序输出样例

1 3 5 8 10

 1 #include<iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 using namespace std;
 6 
 7 bool vis[15];
 8 int map[15][15], d[15], p[15];
 9 const int INF = 999999;
10  
11 int main()
12 {
13     for(int i = 0; i < 10; i++) {
14         for(int j = 0; j < 10; j++) {
15             cin>>map[i][j];
16             if(map[i][j] == -1)
17                 map[i][j] = INF;
18         }
19     }
20     memset(vis, 0, sizeof(vis));
21     for(int i = 0; i < 10; i++) 
22         d[i] = INF;
23     d[0] = 0;
24     for(int i = 0; i < 10; i++) {
25         int cur, min = INF;
26         for(int k = 0; k < 10; k++) {
27             if(d[k] <= min && !vis[k]) {
28                 min = d[k];
29                 cur = k;
30             }
31         }
32         vis[cur] = true;
33         for(int k = 0; k < 10; k++) {
34             if(d[k] > d[cur] + map[cur][k]) {
35                 d[k] = d[cur] + map[cur][k];
36                 p[k] = cur;
37             }
38         }
39     }
40     int dir[15];
41     int x = 9, c = 0;
42     while(x != p[x]) {
43         dir[c++] = x;
44         x = p[x];
45     }
46     dir[c] = 0;
47     for(int i = c; i > 0; i--)
48         cout<<dir[i]+1<<" "; 
49     cout<<dir[0]+1<<endl;
50     return 0;
51 }

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 
 5 #define MAX 999999
 6 int tag[15],map[15][15],dis[15],p[15];
 7 int mark;
 8 
 9 int main()
10 {
11     int min;
12     for(int i=1;i<=10;i++)
13         for(int j=1;j<=10;j++)
14         {
15             cin>>map[i][j];
16             if(map[i][j]==-1)
17                 map[i][j]=MAX;
18         }
19     for(int i=1;i<=10;i++)
20         dis[i]=map[1][i];
21     for(int i=1;i<=10;i++)
22     {
23         min=MAX;
24         for(int j=1;j<=10;j++)
25         {
26             if(tag[j]==0&&dis[j]<min)
27             {
28                 min=dis[j];
29                 mark=j;
30             }
31         }
32         tag[mark]=1;
33         for(int k=1;k<=10;k++)
34         {
35             if(map[mark][k]<MAX)
36             {
37                 if(dis[k]>dis[mark]+map[mark][k])
38                 {
39                     dis[k]=dis[mark]+map[mark][k];
40                     p[k]=mark;
41                 }
42             }
43         }
44     }
45     int dir[15];
46     int x = 10, c = 1;
47     while(x != p[x]) {
48         dir[c++] = x;
49         x = p[x];
50     }
51     dir[c] = 1;
52     for(int i = c; i >= 1; i--)
53         cout<<dir[i]<<" "; 
54     return 0; 
55 }