最短路（临街矩阵）

求最短路：

输入数据：

5 7

1 2 2

1 3 4

1 4 7

2 3 1

2 5 2

3 4 1

3 5 6

Floyed：

1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n,m;
 4 int al[15][15];
 5 void printAL();
 6 void readData(){
 7     memset(al,0x7,sizeof(al));
 8     cin>>n>>m;
 9     for(int i=1;i<=n;i++) al[i][i]=0;
10     for(int i=1;i<=m;i++){
11         int a,b,w;
12         cin>>a>>b>>w;
13         al[a][b]=w;
14         al[b][a]=w;
15     }    
16     
17 }
18 
19 void floyed(){
20     for(int k=1;k<=n;k++){
21         for(int i=1;i<=n;i++){
22             for(int j=1;j<=n;j++){
23                 if(al[i][j]>al[i][k]+al[k][j]){
24                     al[i][j]=al[i][k]+al[k][j];
25                 }
26             }
27         }
28     }
29 }
30 
31 int main(){
32     freopen("shu_in.txt","r",stdin);
33     readData();
34     printAL();
35     floyed();
36     printAL();
37     return 0;
38 } 
39 
40 
41 
42 
43 
44 void printAL(){
45     for(int i=1;i<=n;i++){
46         for(int j=1;j<=n;j++){
47             cout<<setw(10)<<al[i][j]<<" ";
48         }
49         cout<<endl;
50     }
51     cout<<endl;
52 }

Floyed
Dijkstra：

1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n,m;
 4 int al[15][15];
 5 int dis[15];
 6 bool vis[15];
 7 void printAL();
 8 void printDIS();
 9 void readData(){
10     memset(al,0x7,sizeof(al));
11     cin>>n>>m;
12     for(int i=1;i<=n;i++) al[i][i]=0;
13     for(int i=1;i<=m;i++){
14         int a,b,w;
15         cin>>a>>b>>w;
16         al[a][b]=w;
17         al[b][a]=w;
18     }    
19     
20 }
21 
22 void dijkstra(int start){
23     for(int i=1;i<=n;i++) dis[i]=al[start][i];
24     vis[start]=true;
25     
26     for(int k=1;k<=n-1;k++){
27         int minv=0x37777777,min_i;
28         for(int i=1;i<=n;i++){
29             if(!vis[i]&&dis[i]<minv){
30                 minv=dis[i];
31                 min_i=i;
32             }
33         }
34         vis[min_i]=true;
35         for(int i=1;i<=n;i++){
36             if(!vis[i]){
37                 if(dis[i]>dis[min_i]+al[min_i][i]){
38                     dis[i]=dis[min_i]+al[min_i][i];
39                 }
40             }
41         }
42     }
43 
44 }
45 
46 int main(){
47     freopen("shu_in.txt","r",stdin);
48     readData();
49     printAL();
50     dijkstra(1);
51     printDIS();
52     return 0;
53 } 
54 
55 
56 
57 
58 
59 void printAL(){
60     for(int i=1;i<=n;i++){
61         for(int j=1;j<=n;j++){
62             cout<<setw(10)<<al[i][j]<<" ";
63         }
64         cout<<endl;
65     }
66     cout<<endl;
67 }
68 void printDIS(){
69     for(int i=1;i<=n;i++){
70         cout<<setw(10)<<dis[i]<<" ";
71     }
72     cout<<endl;
73 }

Dijkstra
Bellman-Ford：

1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n,m;
 4 int al[15][15];
 5 int dis[15];
 6 void printAL();
 7 void printDIS();
 8 void readData(){
 9     memset(al,0x7,sizeof(al));
10     cin>>n>>m;
11     for(int i=1;i<=n;i++) al[i][i]=0;
12     for(int i=1;i<=m;i++){
13         int a,b,w;
14         cin>>a>>b>>w;
15         al[a][b]=w;
16         al[b][a]=w;
17     }    
18     
19 }
20 
21 void bellman(int start){
22     for(int i=1;i<=n;i++) dis[i]=al[start][i];
23     for(int i=1;i<=n;i++){//轮数 
24         //枚举边
25         for(int j=1;j<=n;j++){
26             for(int k=1;k<=n;k++){
27                 if(dis[j]>dis[k]+al[k][j]){
28                     dis[j]=dis[k]+al[k][j];
29                 } 
30             } 
31         } 
32     }
33 }
34 
35 int main(){
36     freopen("shu_in.txt","r",stdin);
37     readData();
38     printAL();
39     bellman(1);
40     printDIS();
41     return 0;
42 } 
43 
44 
45 
46 
47 
48 void printAL(){
49     for(int i=1;i<=n;i++){
50         for(int j=1;j<=n;j++){
51             cout<<setw(10)<<al[i][j]<<" ";
52         }
53         cout<<endl;
54     }
55     cout<<endl;
56 }
57 void printDIS(){
58     for(int i=1;i<=n;i++){
59         cout<<setw(10)<<dis[i]<<" ";
60     }
61     cout<<endl;
62 }

Bellman-Ford
SPFA:

1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n,m;
 4 int al[15][15];
 5 int dis[15];
 6 queue<int> que;
 7 bool inQue[15];
 8 void printAL();
 9 void printDIS();
10 void readData(){
11     memset(al,0x7,sizeof(al));
12     cin>>n>>m;
13     for(int i=1;i<=n;i++) al[i][i]=0;
14     for(int i=1;i<=m;i++){
15         int a,b,w;
16         cin>>a>>b>>w;
17         al[a][b]=w;
18         al[b][a]=w;
19     }    
20     
21 }
22 
23 void spfa(int start){
24     //dis数组的初始值很大 
25     for(int i=1;i<=n;i++) dis[i]=0x3fffffff;
26     dis[start]=0;
27     que.push(start);
28     inQue[start]=true;
29     while(!que.empty()){
30         int tmp=que.front();
31         que.pop();
32         inQue[tmp]=false;
33         for(int i=1;i<=n;i++){
34             if(dis[i]>dis[tmp]+al[tmp][i]){
35                 dis[i]=dis[tmp]+al[tmp][i];
36                 if(!inQue[i]){
37                     inQue[i]=true;
38                     que.push(i);
39                 }
40             }        
41         }            
42         
43     } 
44 }
45 
46 int main(){
47     freopen("shu_in.txt","r",stdin);
48     readData();
49     printAL();
50     spfa(1);
51     printDIS();
52     return 0;
53 } 
54 
55 
56 
57 
58 
59 void printAL(){
60     for(int i=1;i<=n;i++){
61         for(int j=1;j<=n;j++){
62             cout<<setw(10)<<al[i][j]<<" ";
63         }
64         cout<<endl;
65     }
66     cout<<endl;
67 }
68 void printDIS(){
69     for(int i=1;i<=n;i++){
70         cout<<setw(10)<<dis[i]<<" ";
71     }
72     cout<<endl;
73 }

SPFA
SPFA中dis数组的初始值很大
原文链接: https://www.cnblogs.com/Renyi-Fan/p/7468536.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍