最短路径算法

Dijkstra算法

图G中的起点为顶点s,distTo[]表示G中路径的长度，distTo[v]表示从s到v某条路径的长度。不可达长度设为无穷。T表示已经确定最短路径的节点。

1. distTo[s]初始化为0，更新s到邻接点的距离。s存入T中。

2. 放松 *->v：找到distTo[]内的最短路径distTo[v],更新s到v的邻接点的距离。v存入T中。

distTo[w]=min(distTo[w],disto[v]+edge(v,w));//w为v的邻接点。

3. 循环直到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代表对应顶点的最小路径的前驱矩阵。

1. D − 1 D^{-1} D−1表示初始的邻接矩阵。P初始化为{0,1,2…}。

2. 对于D[i][j]考虑可以经过 v 0 v_0 v0​时的最短路径，更新为 D 0 D^0 D0。

3. 对于 D 0 D^0 D0，考虑可以经过 v 0 , v 1 v_0,v_1 v0​,v1​的最短路径，更新为 D 1 D^1 D1。

4. 循环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;
}

参考：算法四