最短路径算法
Dijkstra算法
图G中的起点为顶点s,distTo[]表示G中路径的长度，distTo[v]表示从s到v某条路径的长度。不可达长度设为无穷。T表示已经确定最短路径的节点。
-
distTo[s]初始化为0，更新s到邻接点的距离。s存入T中。
-
放松 *->v：找到distTo[]内的最短路径distTo[v],更新s到v的邻接点的距离。v存入T中。
distTo[w]=min(distTo[w],disto[v]+edge(v,w));//w为v的邻接点。
- 循环直到T内包含所有节点。可以用另外的矩阵P,P[v]表示s到v的最短路径内v的前一节点。
理解：对于顶点v,前一步已知了顶点所有能抵达的路径的前一部分。s为起点所有路径都得经过这些路径，故对于distTo[v]来说，它是s->v的所有路径里面的最优选。
/**
* @file Dijkstra.cpp
* @author qingfu (qingfu007@gmail.com)
* @brief an algorithm to find the shortest path between two point in an undirected graph
* @version 0.1
* @date 2021-04-06
*
* @copyright Copyright (c) 2021
*
*/
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define INFINITY 2147483647
typedef vector<vector<int>> Graph; //存储邻接表
typedef vector<int> Path; //存储到各个点的最短路径的前置节点
typedef vector<int> Pathtable; //存储到各个点的最短路径权值
void shortestPath_Dijkstra(Graph &edge,Path &p,Pathtable &ptable){
int n=edge.size();
vector<int> final(n,0);
for(int v=0;v<n;++v){
final[v]=0;
p[v]=0;
ptable[v]=edge[0][v];
}
final[0]=1; /*v0为起始点*/
int next=0;
for(int v=1;v<n;++v){
int pmin=INFINITY; /*相对v0的最短距离*/
for(int w=0;w<n;++w){
if(!final[w]&&ptable[w]<pmin){
next=w;
pmin=ptable[w];
}
}
final[next]=1;
for(int w=0;w<n;++w){
if(!final[w]&&edge[next][w]!=INFINITY&&pmin+edge[next][w]<ptable[w]){
p[w]=next;
ptable[w]=pmin+edge[next][w];
}
}
}
}
int main(){
int n=9;
Graph edge(9,vector<int>(9,INFINITY));
Path p(n);
Pathtable ptable(9);
edge[0][1]=1;
edge[0][2]=5;
edge[1][2]=3;
edge[1][3]=7;
edge[1][4]=5;
edge[2][4]=1;
edge[2][5]=7;
edge[3][4]=2;
edge[3][6]=3;
edge[5][7]=5;
edge[6][7]=2;
edge[6][8]=7;
edge[7][8]=4;
for(int i=0;i<n;++i){
edge[i][i]=0;
}
for(int i=0;i<n;++i){
for(int j=0;j<i;++j){
edge[i][j]=edge[j][i];
}
}
shortestPath_Dijkstra(edge,p,ptable);
int k=8;
vector<int> minpath;
while(true){
minpath.push_back(k);
if(k==0||minpath.size()>9) break;
k=p[k];
}
for(int i=minpath.size()-1;i>=0;--i){
cout<<minpath[i];
if(i>0) cout<<"->";
}
cout<<endl;
cout<<"the length of path:"<<ptable.back()<<endl;
return 0;
}
Floyd算法
矩阵D表示顶点到顶点的最短路径权值和的矩阵。
矩阵P代表对应顶点的最小路径的前驱矩阵。
-
D − 1 D^{-1} D−1表示初始的邻接矩阵。P初始化为{0,1,2…}。
-
对于
D[i][j]考虑可以经过 v 0 v_0 v0时的最短路径，更新为 D 0 D^0 D0。 -
对于 D 0 D^0 D0，考虑可以经过 v 0 , v 1 v_0,v_1 v0,v1的最短路径，更新为 D 1 D^1 D1。
-
循环n次。
理解：循环计算从i号顶点到j号顶点只经过前k号点的最短路程。
/**
* @file Floyd.cpp
* @author qingfu (qingfu007@gmail.com)
* @brief Floyd algorithm to find the shortest path
* @version 0.1
* @date 2021-04-06
*
* @copyright Copyright (c) 2021
*
*/
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define INFINITY 2147483647
typedef vector<vector<int>> Graph; //存储邻接表
void shortestPath_Floyd(Graph &D,Graph &P){
int n=D.size();
for(int k=0;k<n;++k){
for(int v=0;v<n;++v){
for(int w=0;w<n;++w){
if(D[v][w]-D[v][k]>D[k][w]){
D[v][w]=D[v][k]+D[k][w];
P[v][w]=P[v][k];
}
}
}
}
}
int main(){
int n=9;
Graph edge(9,vector<int>(9,INFINITY));
Graph P(9,vector<int>(9));
edge[0][1]=1;
edge[0][2]=5;
edge[1][2]=3;
edge[1][3]=7;
edge[1][4]=5;
edge[2][4]=1;
edge[2][5]=7;
edge[3][4]=2;
edge[3][6]=3;
edge[5][7]=5;
edge[6][7]=2;
edge[6][8]=7;
edge[7][8]=4;
for(int i=0;i<n;++i){
edge[i][i]=0;
}
for(int i=0;i<n;++i){
for(int j=0;j<i;++j){
edge[i][j]=edge[j][i];
}
}
Graph D=edge;
for(int j=0;j<n;++j){
for(int i=0;i<n;++i){
P[i][j]=j;
}
}
shortestPath_Floyd(D,P);
cout<<endl;
int k=0;
while(k!=8){
cout<<k<<"->";
k=P[k][8];
}
cout<<8<<endl;
cout<<"the length of path:"<<D[0][8]<<endl;
return 0;
}
参考：算法四