常用四大最短路径算法——Floyd、Dijkstra、Bellman-Ford及其变种
Floyd算法核心思想：找到第三个点代替使两点间的距离更短核心代码就五行：//flody核心for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(M[i][j]>M[i][k]+M[k][j])...
·
目录
热身准备：DFS和BFS
DFS深度优先搜索:
核心思想：一条路走到黑，可以理解为是一种贪心策略；
递归实现模板：一般的套模板就能解决大多数问题
void dfs(int cur){//cur为当前节点编号
cout<<cur<<endl;
sum++;
if(sum==n){//访问完所有节点
return;
}
for(int i=1;i<=n;i++){
if(e[cur][i]==1&&book[i]==0){//如果当前节点和i节点相连并且没有被访问
book[i]=1;
dfs(i);//以顶点i再次出发
book[i]=0;//务必记住将刚才尝试的归位
}
}
return;
}
BFS广度优先搜索：
核心思想：层层递进
核心代码：一般用队列实现
int bfs()
{
queue<pair<int,int>> que; //pair记录城市编号和dis，也可以用结构体
que.push({1,0}); //把起始点加入队列
book[1] = 1; //标记为已在路径中
while(!que.empty())
{
int cur = que.front();
que.pop();
for(int i = 1; i <= n; i++)
{
if(e[cur][i] != MAX && book[i] == 0) //若从cur到i可达且i不在队列中，i入队
{
que.push({i, cur.second+1});
book[i] = 1;
if(i == n) return cur.second; //如果已扩展出目标结点了，返回中转城市数答案
}
}
}
}Floyd算法
核心思想：找到第三个点代替使两点间的距离更短
核心代码就五行：
//flody核心
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(M[i][j]>M[i][k]+M[k][j])
M[i][j] = M[i][k]+M[k][j];
缺点显而易见，算法复杂度太高
//Floyd最短路径
/*
5 8
1 2 2
1 5 10
2 3 3
2 5 7
3 1 4
3 4 4
4 5 5
5 3 3
*/
#include <iostream>
using namespace std;
static const int INF = (1<<21);
int main(){
int M[101][101];
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j){
M[i][j]=0;
}else{
M[i][j]=INF;
}
}
}
int k,t,l;
for(int i=0;i<m;i++){
cin>>k>>t>>l;
k--;
t--;
M[k][t]=l;
}
cout<<"originnal"<<endl;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<M[i][j]<<" ";
}
cout<<endl;
}
//flody核心
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(M[i][j]>M[i][k]+M[k][j]){
M[i][j] = M[i][k]+M[k][j];
}
}
}
}
cout<<"after floyd"<<endl;
//输出最短路径的邻接矩阵
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<M[i][j]<<" ";
}
cout<<endl;
}
return 0;
}Flody-Warshall算法
就比floyd多了一个判断第三点到另外两点之间的距离是不是无穷大，核心思想不变
核心代码
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if((M[k][j]<INF)&&(M[i][k]<INF)&&(M[i][j]>M[i][k]+M[k][j])){
M[i][j] = M[i][k]+M[k][j];
//Floyd最短路径
/*
5 8
1 2 2
1 5 10
2 3 3
2 5 7
3 1 4
3 4 4
4 5 5
5 3 3
*/
#include <iostream>
using namespace std;
static const int INF = (1<<21);
int main(){
int M[101][101];
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j){
M[i][j]=0;
}else{
M[i][j]=INF;
}
}
}
int k,t,l;
for(int i=0;i<m;i++){
cin>>k>>t>>l;
k--;
t--;
M[k][t]=l;
}
cout<<"originnal"<<endl;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<M[i][j]<<" ";
}
cout<<endl;
}
//flody-Warshall核心
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if((M[k][j]<INF)&&(M[i][k]<INF)&&(M[i][j]>M[i][k]+M[k][j])){
M[i][j] = M[i][k]+M[k][j];
}
}
}
}
cout<<"after floyd-warshall"<<endl;
//输出最短路径的邻接矩阵
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<M[i][j]<<" ";
}
cout<<endl;
}
return 0;
}Dijkstra最短路径算法——计算单源最短路径
核心思想：通过边实现松弛
核心代码：
- 通过dis数组存储距离目标结点距离;book记录已知最短路程的顶点;
- 遍历一遍找到距离目标节点最短的节点；
- 以这个节点为拓展，遍历一边找到最短路路径；
- 将上述步骤重复n-1次可以找到左右最短路径；
为什么要重复n-1次呢？？
因为上述三个步骤只能找出两点之间有一个中介点的最短路径的情况，重复n-1边就可以找出中间有1~n-1个中介点的情况！
for(int i=0;i<n-1;i++){//重复n-1次可以找到所有最短路径
minnum = INF;//初始化最小值为无穷大
for(int j=0;j<n;j++){
if(book[j]==0&&dis[j]<minnum){
minnum = dis[j];//更新最小值,找到距离0节点最近的节点
u=j;
}
}
book[u]=1;//节点u已经找到最短路径
//以距离0节点最近的节点u进行拓展;遍历一遍寻找最短路径
for(int v=0;v<n;v++){
if(M[u][v]<INF){
if(dis[v]>dis[u]+M[u][v]){
dis[v]=dis[u]+M[u][v];
}
}
}
}//Dijkstra最短路径
/*
5 8
1 2 2
1 5 10
2 3 3
2 5 7
3 1 4
3 4 4
4 5 5
5 3 3
*/
#include <iostream>
using namespace std;
static const int INF = (1<<21);
int main(){
int dis[101],book[101];//dis存储目标节点到其他节点的单元最短路径;book记录已知最短路程的顶点
int M[101][101];
int n,m;
cin>>n>>m;
//初始化邻接矩阵
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j){
M[i][j]=0;
}else{
M[i][j]=INF;
}
}
}
int k,t,l;
//读入邻接矩阵
for(int i=0;i<m;i++){
cin>>k>>t>>l;
k--;
t--;
M[k][t]=l;
}
//初始化dis数组
for(int i=0;i<n;i++){
dis[i]=M[0][i];//因为是求0节点的单源最短路径
}
for(int i=0;i<n;i++){
book[i]=0;//初始化book数组
}
int minnum;
int u;
for(int i=0;i<n-1;i++){//重复n-1次可以找到所有最短路径
minnum = INF;//初始化最小值为无穷大
for(int j=0;j<n;j++){
if(book[j]==0&&dis[j]<minnum){
minnum = dis[j];//更新最小值,找到距离0节点最近的节点
u=j;
}
}
book[u]=1;//节点u已经找到最短路径
//以距离0节点最近的节点u进行拓展;遍历一遍寻找最短路径
for(int v=0;v<n;v++){
if(M[u][v]<INF){
if(dis[v]>dis[u]+M[u][v]){
dis[v]=dis[u]+M[u][v];
}
}
}
}
for(int i=0;i<n;i++){
cout<<dis[i]<<" ";
}
return 0;
}
Bellman-Ford——解决负数权重的图
核心思想：对边的松弛
核心代码：
- dis数组存储到目标节点的最短距离
- 用邻接矩阵表示
- u[i]、v[i]、w[i]表示从节点u到v权重为w的边
- 能否通过结点v[i]到结点u[i]权重为w[i]的边使得1号结点到v[i]的顶点的距离变短
// Bellman-Ford核心
for(int k=0;k<n-1;k++){//进行n-1轮重复遍历可以考虑完所有情况
for(int i=0;i<m;i++){
//能否通过结点v[i]到结点u[i]权重为w[i]的边使得1号结点到v[i]的顶点的距离变短
if(dis[v[i]]>dis[u[i]]+w[i])
dis[v[i]] = dis[u[i]] + w[i];
}
}
//Bellman-Ford
/*
4 5
1 4 9
2 4 6
1 2 5
4 3 8
1 3 7
*/
#include <iostream>
using namespace std;
static const int INF = (1<<21);
int main(){
int dis[101];//dis存储目标节点到其他节点的单元最短路径
int u[101],v[101],w[101];//表示顶点u[i]到v[i]这条边的权值为w[i]
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++){
cin>>u[i]>>v[i]>>w[i];
}
for(int i=1;i<n;i++){
dis[i]=INF;
}
dis[0]=0;
// Bellman-Ford核心
for(int k=0;k<n-1;k++){//进行n-1轮重复遍历可以考虑完所有情况
for(int i=0;i<m;i++){
//能否通过结点v[i]到结点u[i]权重为w[i]的边使得1号结点到v[i]的顶点的距离变短
if(dis[v[i]]>dis[u[i]]+w[i])
dis[v[i]] = dis[u[i]] + w[i];
}
}
for(int i=0;i<n;i++){
cout<<dis[i]<<" ";
}
return 0;
}Bellman-Ford拓展——判断是否有负数权重的边
核心思想：
判断是否仍然存在通过结点v[i]到结点u[i]权重为w[i]的边使得1号结点到v[i]的顶点的距离变短的情况，说明存在负数权重的边、
核心代码：
for(int i=0;i<m;i++){
//仍然存在通过结点v[i]到结点u[i]权重为w[i]的边使得1号结点到v[i]的顶点的距离变短的情况
//说明存在负数权重的边
if(dis[v[i]]>dis[u[i]]+w[i]){
dis[v[i]] = dis[u[i]] + w[i];
cout<<"yes！"<<endl;
break;
}
}//Bellman-Ford负数权重的边
/*
5 5
1 2 2
0 1 -3
0 4 5
3 4 2
2 4 3
*/
#include <iostream>
using namespace std;
static const int INF = (1<<21);
int main(){
int dis[101];//dis存储目标节点到其他节点的单元最短路径
int u[101],v[101],w[101];//表示顶点u[i]到v[i]这条边的权值为w[i]
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++){
cin>>u[i]>>v[i]>>w[i];
}
for(int i=0;i<n;i++){
dis[i]=INF;
}
dis[0]=0;
// Bellman-Ford核心
for(int k=0;k<n-1;k++){//进行n-1轮重复遍历可以考虑完所有情况
for(int i=0;i<m;i++){
//能否通过结点v[i]到结点u[i]权重为w[i]的边使得1号结点到v[i]的顶点的距离变短
if(dis[v[i]]>dis[u[i]]+w[i]){
dis[v[i]] = dis[u[i]] + w[i];
cout<<dis[v[i]]<<"i"<<i<<" "<<"k"<<k<<endl;
}
}
}
for(int i=0;i<n;i++){
cout<<dis[i]<<" ";
}
for(int i=0;i<m;i++){
//仍然存在通过结点v[i]到结点u[i]权重为w[i]的边使得1号结点到v[i]的顶点的距离变短的情况
//说明存在负数权重的边
if(dis[v[i]]>dis[u[i]]+w[i]){
dis[v[i]] = dis[u[i]] + w[i];
cout<<"yes！"<<endl;
break;
}
}
return 0;
}四大算法比较
小试牛刀——单元最短路径一道例题
from AOJ
Single Source Shortest Path
For a given weighted graph G=(V,E)G=(V,E), find the shortest path from a source to each vertex. For each vertex uu, print the total weight of edges on the shortest path from vertex 00 to uu.
Input
In the first line, an integer nn denoting the number of vertices in GG is given. In the following nn lines, adjacency lists for each vertex uu are respectively given in the following format:
uu kk v1v1 c1c1 v2v2 c2c2 ... vkvk ckck
Vertices in GG are named with IDs 0,1,...,n−10,1,...,n−1. uu is ID of the target vertex and kk denotes its degree. vi(i=1,2,...k)vi(i=1,2,...k) denote IDs of vertices adjacent to uu and cici denotes the weight of a directed edge connecting uu and vivi (from uu to vivi).
Output
For each vertex, print its ID and the distance separated by a space character in a line respectively. Print in order of vertex IDs.
Constraints
- 1≤≤n≤100
- 0≤ci≤100,0000≤ci≤100,000
- |E|≤10,000|E|≤10,000
- All vertices are reachable from vertex 00
Sample Input 1
5 0 3 2 3 3 1 1 2 1 2 0 2 3 4 2 3 0 3 3 1 4 1 3 4 2 1 0 1 1 4 4 3 4 2 2 1 3 3Sample Output 1
0 0 1 2 2 2 3 1 4 3Reference
Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.
Source: https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_12_B
这里n很小，100以内，所以Floyd可以解决；
如果n变大，要换用Dijkstra或者Berllan！
//Single_Source_Shortest_Path_I
/*
5
0 3 2 3 3 1 1 2
1 2 0 2 3 4
2 3 0 3 3 1 4 1
3 4 2 1 0 1 1 4 4 3
4 2 2 1 3 3
*/
#include <iostream>
using namespace std;
static const int INF = (1<<21);
int main(){
int n;
cin>>n;
int M[100][100];
for(int i=0;i<100;i++){
for(int j=0;j<100;j++){
if(i==j)
M[i][j]=0;
else
M[i][j]=INF;
}
}
int w,m,v,u;
for(int i=0;i<n;i++){
cin>>u>>m;
for(int j=0;j<m;j++){
cin>>v>>w;
M[u][v]=w;
}
}
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(M[i][j]>M[i][k]+M[k][j])
M[i][j]=M[i][k]+M[k][j];
}
}
}
for(int i=0;i<n;i++){
cout<<i<<" "<<M[0][i]<<endl;
}
return 0;
}
腾讯云面向开发者汇聚海量精品云计算使用和开发经验，营造开放的云计算技术生态圈。
更多推荐
4
0- 0
已为社区贡献2条内容
所有评论(0)