图结构练习——最短路径
Time Limit: 1000MS Memory limit: 65536K
题目描述
给定一个带权无向图，求节点1到节点n的最短路径。
输入
输入包含多组数据，格式如下。
第一行包括两个整数n m，代表节点个数和边的个数。(n<=100)
剩下m行每行3个正整数a b c，代表节点a和节点b之间有一条边，权值为c。
输出
每组输出占一行，仅输出从1到n的最短路径权值。（保证最短路径存在）
示例输入
3 2
1 2 1
1 3 1
1 0
示例输出
1
0
提示
两种算法，弗洛伊德时间复杂度为O（N^3）
迪杰斯特拉时间复杂度为O（N^2）
示例程序
算法一：
弗洛伊德算法：Floyed-Warshall
根据经验，如果要让任意两个顶点之间的路程变短，只能引入
第三个点通过这个点中转求得。
假如中转点是顶点K，只需判断mp[i][k]+mp[k][j]是否比mp[i][j]小即可。
基本思想是：最开始只允许经过一个顶点进行中转，接下来++i实现
从i号顶点到j号顶点只经过前k号点的最短路径。
Floyd算法完整代码：
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int main()
{
int n, m;
int mp[112][112];
while(cin >> n >> m)
{
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(i == j)
mp[i][j] = 0;
else
mp[i][j] = INF;
}
}
while(m--)
{
int a, b, c;
cin >> a >> b >> c;
if(mp[a][b] > c)
mp[a][b] = mp[b][a] = c;
}
Floyd 弗洛伊德算法核心语句：
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(mp[i][j] != INF)
{
for(int k = 1; k <= n; k++)
{
mp[j][k] = min(mp[j][k], mp[j][i]+mp[i][k]);
}
}
}
}
// for(int k = 1; k <= n; k++)
// {
// for(int i = 1; i <= n; i++)
// {
// for(int j = 1; j <= n; j++)
// {
// if(mp[i][k] < INF&&mp[k][j] < INF&&mp[i][j] > mp[i][j]+mp[k][j])
// mp[i][j] = mp[i][k]+mp[k][j];
// }
// }
// }
cout << mp[1][n] << endl;
}
return 0;
}
算法二：
迪杰斯特拉 Dijkstra -- 单源最短路
此算法的基本思想是：每次找到离源点最近的顶点，然后以该顶点为
中心进行扩展，（松弛）最终得到源点到其余所有点的
最短路径。
此算法基本步骤如下：
1：
将所有的顶点分为两部分：已知最短路程的顶点集合P和未知最短
路径的顶点集合Q。最开始，集合P中只有源点一个顶点。我们这里用
一个book数组来记录那些点在集合P中。例如对于某个顶点i，如果
book[i]为1则表示这个顶点在集合P中，如果book[i]为0则表示这个顶
点在集合Q中。
2：
设置源点s到自己的最短路径为0即dis[s]=0。若存在有源点能直
接到达的顶点i，则把dis[i]设为mp[s][i]。同时把所有其他（源点不
能直接到达的）顶点的最短路径设为无穷。
3：
在集合Q的所有顶点中选择一个离源点s最近的顶点u(即dis[u]最小)
加入的集合P。并考察所有以点u为起点的边，对每一条边进行松弛操作。
例如存在一条从u到v的边，那么可以通过将边u->v添加到尾部来拓展一
条从s到v的路径，这条路径的长度是dis[u]+mp[u][v]。如果这个值比目
前一致的dis[v]的值要小，我们可以用新值来替代当前dis[v]中的值。
4：
重复第3步，如果集合Q为空，算法结束。最终dis数组中的值就是
源点到所有定点的最短路径。
完整的Dijkstra算法代码：
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int mp[110][110];
int book[110], dis[110];
int Min, u;
int main()
{
int m, n;
while(cin >> n >> m)
{
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
{
if(i == j)
mp[i][j] = 0;
else
mp[i][j] = INF;
}
while(m--)
{
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
if(mp[a][b] > c)
{
mp[a][b] = mp[b][a] = c;
}
}
for(int i = 1; i <= n; i++)
dis[i] = mp[1][i];
for(int i = 1; i <= n; i++)
book[i] = 0;
book[1] = 1;
Dijkstra算法核心语句：
for(int i = 1; i <= n-1; i++)
{
Min = INF;
for(int j = 1; j <= n; j++)
{
if(!book[j]&&dis[j] < Min)
{
Min = dis[j];
u = j;
}
}
book[u] = 1;
for(int v = 1; v <= n; v++)
{
if(mp[u][v] < INF)
{
dis[v] = min(dis[v], dis[u]+mp[u][v]);
}
}
}
printf("%d\n", dis[n]);
}
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-1310367.html
