2.7. 最短路径
参考 最短路径文章
基本结构和思想
dist[n] 表示起始点startN 到 具体第N个点的距离。
path[n] 表示当前点位到达的上一个点位的索引。 比如 最短路径 1 3 4 这样走， 那path[4]=3 。
s[n] 表示当前点在S里面还是在U里面的， 通过s[i]==1 表示在S， s[i]]=0 表示在U里面。
startN 表示我起点的位置索引。
思想
1. 初始化 dist path s ;
2. while ( s元素个数<n)
2.1 在dist[n] 中找到最小值， 下标为k .
2.2 修改数组dist path
2.3 将k点位加入到S ;
样例图
2.7.1. dijskra算法
1#include <stdio.h>
2#include <string.h>
3
4#define MaxV 9999999
5
6const int N=510;
7
8int g[N][N]; //稠密图所以用邻接矩阵存储，表示i点和j点之间边的长度
9int dist[N]; //每一个点到源点的距离
10int path[N]; //记录路径。到到第N个点前一个点是什么点位。
11int s[N]; //记录该点的最短距离是否已经确定
12
13int n,m, startN;
14
15
16
17int findMinDist(){
18 int minV = MaxV ;
19 for (int i = 0; i <n ; ++i) {
20 if (s[i]==0 && dist[i] <minV){
21 return i ;
22 }
23 }
24 return -1 ;
25}
26
27
28int Dijkstra()
29{
30 // 根据邻接矩阵填充dist ,path
31 for (int i = 0; i < n; ++i) {
32 dist[i] = g[startN][i] ;
33 if (dist[i] !=MaxV){
34 path[i] = startN ;
35 }else{
36 path[i]= -1;
37 }
38 }
39 // 初始化s , 开始的时候只是将初始节点标记为S.
40 for (int i = 0; i <n ; ++i) {
41 s[i] = 0 ;
42 }
43 s[startN] = 1 ;
44
45 int sCount = 1;
46 while (sCount < n ){
47 int minN = findMinDist ();
48 s[minN] = 1;
49 for (int i = 0; i < n; ++i) {
50 if (s[i]==0 && dist[i] > dist[minN]+g[minN][i]){
51 dist[i] = dist[minN]+g[minN][i] ;
52 path[i] = minN;
53 }
54 }
55 sCount +=1;
56 }
57
58}
59
60
61
62
63void InitDemo(){
64
65 n = 7 ;
66 startN = 0 ;
67
68 for (int i = 0; i < n; ++i) {
69 for (int j = 0; j <n ; ++j) {
70 g[i][j] = MaxV ;
71 }
72 }
73
74 for (int i = 0; i < n; ++i) {
75 g[i][i] = 0;
76 }
77
78 g[0][1] = 4;
79 g[0][2] = 6;
80 g[0][3]= 6;
81
82 g[1][2]= 1;
83 g[1][4]= 7 ;
84
85 g[2][4]=6;
86 g[2][5]=4;
87
88 g[3][2] = 2;
89 g[3][5]= 5;
90
91 g[4][6]= 6;
92
93 g[5][4] = 1;
94 g[5][6] = 8 ;
95
96
97}
98
99
100
101int main()
102{
103 printf("start \n");
104 InitDemo() ;
105 for (int i = 0; i<n; ++i) {
106 for (int j = 0; j<n; ++j) {
107 printf("%d\t", g[i][j]);
108 }
109 printf("\n");
110 }
111 Dijkstra() ;
112 for (int i = 0; i<n; ++i) {
113 printf("%d=>%d %d\n",startN,i,dist[i]) ;
114 }
115
116 return 0;
117}
2.7.2. floyd算法
1#include <stdio.h>
2#include <string.h>
3
4#define MaxV 9999999
5
6const int N=510;
7
8int g[N][N]; //稠密图所以用邻接矩阵存储，表示i点和j点之间边的长度
9int dist[N][N]; //i = > j 的距离
10char* path[N][N]; // i => j 经过路径。
11int s[N]; //记录该点的最短距离是否已经确定
12
13int n;
14
15
16
17int Floyd()
18{
19 // 根据邻接矩阵填充dist ,path
20 for (int i = 0; i < n; ++i) {
21 for (int j = 0; j <n ; ++j) {
22 dist[i][j] = g[i][j] ;
23 if (dist[i][j] !=MaxV){
24 //path[i][j] = char('0' +i ) + char('0' +j )
25 }else{
26 path[i][j]= "" ;
27 }
28 }
29
30 }
31
32 for (int i = 0; i < n ; ++i) {
33 for (int j = 0; j <n ; ++j) {
34 for (int k = 0; k <n ; ++k) {
35 if (dist[i][k] + dist[k][j] < dist[i][j]){
36 dist[i][j] = dist[i][k] + dist[k][j] ;
37 //path[i][j] = path[i][k] + path[k][j] ;
38 }
39 }
40 }
41 }
42
43}
44
45
46
47
48void InitDemo(){
49
50 n = 5 ;
51
52 for (int i = 0; i < n; ++i) {
53 for (int j = 0; j <n ; ++j) {
54 g[i][j] = MaxV ;
55 }
56 }
57
58 for (int i = 0; i < n; ++i) {
59 g[i][i] = 0;
60 }
61
62 g[0][1] = 10 ;
63 g[0][3] = 30 ;
64 g[0][4] = 100 ;
65
66 g[1][0] = 10 ;
67 g[1][2]=50 ;
68
69 g[2][1] =50 ;
70 g[2][3]=20 ;
71 g[2][4]= 10 ;
72
73 g[3][0]=30 ;
74 g[3][2]= 20 ;
75 g[3][4]= 60 ;
76
77 g[4][0] =100 ;
78 g[4][2]= 10 ;
79 g[4][3]=60 ;
80
81
82}
83
84
85
86int main()
87{
88 printf("start \n");
89 InitDemo() ;
90 for (int i = 0; i<n; ++i) {
91 for (int j = 0; j<n; ++j) {
92 printf("%d\t", g[i][j]);
93 }
94 printf("\n");
95 }
96 Floyd() ;
97 for (int i = 0; i<n; ++i) {
98 for (int j = 0; j <n ; ++j) {
99 if (i==j){
100 continue;
101 }
102 printf("%d=>%d %d\n",i,j,dist[i][j]) ;
103 }
104
105 }
106
107 return 0;
108}