首页 > 代码库 > 第六章 最短路径——有向图（Floyd-Warshall、Dijkstra、Bellman-Ford）

第六章 最短路径——有向图（Floyd-Warshall、Dijkstra、Bellman-Ford）

2024-10-11 19:12:39   234人阅读

一、Floyd-Warshall——加入点（多源最短路径，核心算法只有五行）

城市之间的最短路径

输入：
4 8
1 2 2 
1 3 6
1 4 4
2 3 3
3 1 7
3 4 1
4 1 5
4 3 12
输出：
0 2 5 4
9 0 3 4
6 8 0 1
5 7 10 0
技术分享 
 1 #include <stdio.h>
 2 #define Max 99999
 3 int main()
 4 {
 5     int map[10][10];
 6     int n, m, x, y, t;
 7     int i, j, k;
 8     scanf("%d%d",&n,&m);
 9     for (i = 1;i <= n;i++)
10     {
11         for (j = 1;j <= n;j++)
12         {
13             if (i == j)
14                 map[i][j] = 0;
15             else
16                 map[i][j] = Max;
17         }
18     }
19     for (i = 1;i <= m;i++)
20     {
21         scanf("%d%d%d",&x,&y,&t);
22         map[x][y] = t;
23     }
24     for (k = 1;k <= n;k++)
25     {
26         for (i = 1;i <= n;i++)
27         {
28             for (j = 1;j <= n;j++)
29             {
30                 if (map[i][k] < Max&&map[k][j]<Max&&map[i][j]>map[i][k] + map[k][j])
31                 {
32                     map[i][j] = map[i][k] + map[k][j];
33                 }
34             }
35         }
36     }
37     for (i = 1;i <= n;i++)
38     {
39         for (j = 1;j <= n;j++)
40             printf("%d ",map[i][j]);
41         printf("\n");
42     }
43     return 0;
44 }
View Code

 二、Dijkstra——加入边（单源最短路径）

输入：第一行n（顶点个数，编号从1开始）,m（边的条数）；接下来m行，每行3个数x，y，z，表示顶点x到y边的权值为z
6 9
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4
输出：1号顶点到其余各个顶点（1，2，3，4，5，6）的最短距离
0 1 8 4 13 17
 
使用二位数组存储边
技术分享 
 1 #include <stdio.h>
 2 #define Max 99999
 3 int main()
 4 {
 5     int map[10][10],dis[10],book[10];
 6     int n, m, x, y, t;
 7     int i, j, k;
 8     int min,mini;
 9     scanf("%d%d",&n,&m);
10     for (i = 1;i <= n;i++)
11     {
12         for (j = 1;j <= n;j++)
13         {
14             if (i == j)
15                 map[i][j] = 0;
16             else
17                 map[i][j] = Max;
18         }
19     }
20     for (i = 1;i <= m;i++)
21     {
22         scanf("%d%d%d",&x,&y,&t);
23         map[x][y] = t;
24     }
25     for (i = 1;i <= n;i++)
26         dis[i] = map[1][i];
27     for (i = 1;i <= n;i++)
28         book[i] = 0;
29     book[1] = 1;
30     for (i = 1;i <n;i++)
31     {
32         min = Max;
33         for (j = 1;j <= n;j++)
34         {
35             if (book[j] == 0 && min > dis[j])
36             {
37                 min = dis[j];
38                 mini = j;
39             }
40         }
41         book[mini] = 1;
42         for (j = 1;j <= n;j++)
43         {
44             if (map[mini][j] < Max)
45             {
46                 if (dis[j] > dis[mini] + map[mini][j])
47                 {
48                     dis[j] = dis[mini] + map[mini][j];
49                 }
50             }
51         }
52     }
53     for (i = 1;i <= n;i++)
54     {
55         printf("%d ",dis[i]);     
56     }
57     printf("\n");
58     return 0;
59 }
View Code

使用邻接表存储边

 

第六章 最短路径——有向图（Floyd-Warshall、Dijkstra、Bellman-Ford）


联系
我们