# 最短路

2021-07-20 12:14:01 软件工程小施同学

Problem Description

Input

Output

Sample Input
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0

Sample Output
3
2

最最最简单的最短路问题！写了三个常用求最短路的算法：floyd、djikstra、spfa，都能轻松解决！

``````#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <queue>
using namespace std;
const int N = 105;
const int INF = 99999999;
int map[N][N], dist[N];
bool visit[N];
int n, m;
void init()     //初始化
{
int i, j;
for(i = 1; i < N; i++)
{
for(j = 1; j < N; j++)
{
if(i == j) map[i][j] = 0;
else map[i][j] = map[j][i] = INF;
}
}
}
void input()    //输入函数
{
int vi, vj, cost;
while(m--)
{
scanf("%d %d %d", &vi, &vj, &cost);
if(cost < map[vi][vj])
map[vi][vj] = map[vj][vi] = cost;
}
}
void floyd()    //Floyd算法
{
int i, j, k;
for(k = 1; k <= n; k++)     //k为中间点
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
if(map[i][k] + map[k][j] <  map[i][j])
map[i][j] = map[i][k] + map[k][j];
}
void dijk()     //Dijkstra算法
{
int i, j, next, MIN;
memset(visit, false, sizeof(visit));
for(i = 1; i <= n; i++) dist[i] = INF;
dist[1] = 0;
for(i = 1; i <= n; i++)
{
MIN = INF;
for(j = 1; j <= n; j++)
if(!visit[j] && dist[j] <= MIN)
MIN = dist[next=j];
if(MIN == INF) break;
visit[next] = true;            //这里的visit用于表示该点是否在已处理点集中
for(j = 1; j <= n; j++)
if(!visit[j] && dist[j] > dist[next] + map[next][j])
dist[j] = dist[next] + map[next][j];
}
}
void spfa()     //SPFA算法
{
int i, now;
memset(visit, false, sizeof(visit));
for(i = 1; i <= n; i++) dist[i] = INF;
dist[1] = 0;
queue<int> Q;
Q.push(1);
visit[1] = true;
while(!Q.empty())
{
now = Q.front();
Q.pop();
visit[now] = false;
for(i = 1; i <= n; i++)
{
if(dist[i] > dist[now] + map[now][i])
{
dist[i] = dist[now] + map[now][i];
if(visit[i] == 0)
{
Q.push(i);
visit[i] = true;    //这里的visit用于表示是否在队列中
}
}
}
}
}
int main()
{
while(scanf("%d %d", &n, &m))
{
if(!n || !m) break;
init();
input();
//floyd();
//dijk();
spfa();
//printf("%d\n", map[1][n]);
printf("%d\n", dist[n]);
}
return 0;
}```

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
```

https://blog.51cto.com/u_15077160/2915331