最短路径（图）

矫情吗；* 2022-06-02 03:59 164阅读 0赞

## **Dijkstra算法** ##

Dijkstra算法为求带权图中从一个顶点（此处假设为Vo）到其它各顶点的最短路径，按路径长度递增的次序产生最短路径，假设所有权值非负。

储存结构：

1.图采用邻接矩阵表示法，对角线元素初值均取0。

2.数组dist\[\]: dist\[i\]最终储存Vo到Vi的最短路径及最短路径上Vi的前驱顶点（计算过程为距离值，可能会被调整）。  
说明：

1.dist\[ \]看成V集合，其中U指从Vo到一个顶点最短路径的所有顶点，V-U指未确定最短路径的顶点集合。  
2.初始化dist时，集合U只有Vo，其对应的距离值为0；集合V中Vi的距离值为边（Vo，Vi）的权，若Vo和Vi之间无直接边，则Vi的距离值为MAX。

基本思想：

1）从集合V中选择距离值最小的顶点Vmin加入到集合U（可通过修改对角线元素值为1来表示）  
  
2）因为上面选出的Vmin放到U时，如果Vmin可能是Vo到其它顶点V\[i\]最短路径上的一个顶点，这使得dist\[i\]的距离值减小，所以这时，需要根据min值，对集合V-U中各顶点的距离值进行调整：如果Vo到Vi的距离值比原来的距离值小，则修改Vi的距离值dist\[i\].length，否则不修改。  
  
  
3）重复1）2），直到从Vo可以到达的所有顶点都被放入集合U为止。

C++代码实现：

#include <iostream>
    #define Vextype int
    #define Adjtype int
    #define VN 2018
    #define MAX 10000
    using namespace std;
    
    typedef struct
    {
        Vextype vex[VN][VN];
        Adjtype arc[VN][VN];
    }GraphMatrix;

typedef struct{
        Adjtype length;//shortest path
        int prevex;//Vi的前驱顶点
    }Path;
    Path dist[VN];
    void init(GraphMatrix *pgraph,Path *dist)
    {
        dist[0].length=dist[0].prevex=0;
        pgraph->arc[0][0]=1;//用矩阵对角线元素表示U，为1表示在U中
        for(int i=1;i<VN;i++){//初始化U-V中顶点的距离值
            dist[i].length=pgraph->arc[0][i];
            if(dist[i].length!=MAX) dist[i].prevex=0;
            else dist[i].prevex=-1;
        }
    }
    void dijkstra(GraphMatrix *pgraph,Path *dist)
    {
        init(pgraph,dist);//初始化，U中只有Vo
        Adjtype minw;
        int mv;
        for(int i=1;i<VN;i++){
            minw=MAX; mv=0;
            for(int j=1;j<VN;j++)//在V-U中选出距离Vo最近的顶点
                if(pgraph->arc[j][j]!=1 && minw>dist[j].length){
                    minw=dist[j].length; mv=j;
                }
            if(mv==0)    break;//Vo与V-U的顶点不连通，结束
            pgraph->arc[mv][mv]=1;//顶点mv加入U
            for(int i=1;i<VN;i++){//调整V-U顶点的已知最短路径
                if(pgraph->arc[i][i]!=1 && dist[i].length>dist[mv].length+pgraph->arc[mv][i]){
                    dist[i].prevex=mv;
                    dist[i].length=dist[mv].length+pgraph->arc[mv][i];  }
            }
        }
    }

时间复杂度为O（n^2)。

## Floyd算法 ##

为求带权图中每一对顶点间的最短路径，可以依次把图中每个顶点作为起始点，利用Dijkstra算法求出每对顶点之间的最短路径，时间复杂度为O（n^3）。

但另一种方法Floyd算法更易理解，时间复杂度也是O（n^3）。

储存结构：

1.图也是用邻接矩阵表示法，对角线元素初值均取0。

2.定义一个与原始关系矩阵一样的矩阵，处理过程中存放每对顶点间的距离值。

3.再定义一个与原始矩阵同样大小的整数数组，存放Vi到Vj最短路径上Vi的后继顶点的下标值。

基本思想：

Floyd算法以关系矩阵为基础，将其看作是没有经过任何中间结点的每对顶点间的最短路径，然后经过多次迭代修改，每次增加一个新的结点，如果该结点作为中间结点，判断此路径是否小于原来的路径，若是则修改原来的路径（取小的值）。直到所有结点都增加进去，得到每对顶点间的最短路径。比如，求V 0到V 1的最短路径，由ppath->a\[0\]\[1\]可知最短路径的值，由ppath->nextvex\[0\]\[1\]得到最短路径上，V 0的下一个顶点V k，由ppah->nextvex\[k\]\[1\]得到V k的下一个顶点，以此类推，直到顶点V 1，从而得到最短路径。

C++代码实现：

typedef struct{
        Adjtype a[VN][VN];
        int nextvex[VN][VN];
    }Shortpath;
    void floyd(GraphMatrix *pgraph,Shortpath *ppath)
    {
        for(int i=0;i<VN;i++)//initialize
            for(int j=0;j<VN;j++){
                ppath->a[i][j]=pgraph->arc[i][j];
                if(pgraph->arc[i][j]!=MAX)  ppath->nextvex[i][j]=j;
                else    ppath->nextvex[i][j]=-1;
            }
        for(int k=0;k<VN;k++)//iterate calculate *ppath
            for(int i=0;i<VN;i++)
                for(int j=0;j<VN;j++){
                    if(pgraph->arc[i][k]==MAX||pgraph->arc[k][j]==MAX)  continue;
                    if(ppath->a[i][j]>pgraph->arc[i][k]+pgraph->arc[k][j]){//revise *ppath
                        ppath->a[i][j]=pgraph->arc[i][k]+pgraph->arc[k][j];
                        ppath->nextvex[i][j]=ppath->nextvex[i][k];
                    }
                }
    }