最短路径

最短路径

在网图和非网图中，最短路径的含义是不同的。由于非网图没有边上的权值，所谓的最短路径其实是指两顶点之间经过的边数最少的路径；而对于网图来说，最短路径指的是两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点。一般有两种最短路径。

第一种：从某个源点到其余各顶点的最短路径问题：Dijistra算法：

1.初始化：先找出从源点v0到各终点vk的直达路径(v0,vk),即通过一条弧到达的路径；
2.选择：从这些路径中找出一条长度最短的路径(v0,u)；
3.更新：然后对其余各条路径进行适当调整：
若在图中存在弧(u,vk)，且(v0,u)+(u,vk)<(v0,vk),则以路径(v0,u,vk)代替(v0,vk)。在调整后的各条路径中，再找长度最短的路径，依次类推。
即按照路径长度递增次序产生最短路径，具体来说：
1.把V分成两组
（1）S：已求出最短路径的顶点的集合；
（2）T=V-S:尚未确定最短路径的顶点集合。
2.将T中顶点按最短路径递增的次序加入到S中
保证：
（1）从源点v0到S中各顶点的最短路径都不大于从v0到T中任何顶点的最短路径长度。
（2）每个顶点对应一个距离值：
S中顶点：从v0到此顶点的最短路径长度。
T中顶点：从v0到此顶点的只包括S中顶点作中间顶点的最短路径长度。

第二种：求所有顶点间的最短路径

方法1：每次以一个顶点为源点，重复执行Dijkstra算法n次
方法2：弗洛伊德（Floyd）算法
思想：逐个顶点试探，从vi到vj的所有可能存在的路径中，选出一条长度最短的路径。

代码示例

关于图的邻接矩阵结构创建可查看以前的文章https://www.jianshu.com/p/b50ba1b3c327
MGraph.h

//Dijkstra算法（求有向网G的v0顶点到其余顶点v最短路径P[v]及带权长度D[v]）
typedef int Patharc[MAXVEX];                    //存储最短路径下标的数组
typedef int ShortPathTable[MAXVEX];             //存储到各点最短路径的权值之和

//P[v]的值为前驱结点下标，D[v]表示v0到v的最短路径长度之和
void ShortestPath_Dijkstra(MGraph  G, int v0, Patharc P, ShortPathTable D);

//弗洛伊德（Floyd）算法，求网图G中各顶点v到其余顶点w最短路径P[v][w]及带权长度D[v][w]
typedef int Pathmatrix[MAXVEX][MAXVEX];
typedef int ShortPathTable_floyd[MAXVEX][MAXVEX];
void ShortestPath_Floyd(MGraph G, Pathmatrix P, ShortPathTable_floyd D);

MGraph.cpp

//P[v]的值为前驱结点下标，D[v]表示v0到v的最短路径长度之和
void ShortestPath_Dijkstra(MGraph  G, int v0, Patharc P, ShortPathTable D)
{
    //step1:初始化
    int final[MAXVEX] = { 0 };                                  //final[w]=1标志求得顶点v0->v1的最短路径，初始化为未知最短路径
    for (int v = 0; v < G.numVertexes; v++)
    {
        P[v] = 0;                                               //初始化路径数组为0
        D[v] = G.arc[v0][v];                                    //初始化v0点与其他顶点之间的路径
    }

    D[v0] = 0;                                                  //v0与v0之间的路径为0
    final[v0] = 1;                                              //v0至v0不需要求路径

    int min, k;
    //step2:开始主循环,更新每个顶点距离v0的距离
    for (int i = 1; i < G.numVertexes; i++)
    {
        min = MAXEDGE;                                          //当前距离v0顶点的最近距离
        for (int w = 0; w < G.numVertexes; w++)
        {
            if (!final[w] && D[w] < min)                        //到w顶点的最短路径还未求得，当前状态距离顶点k最近
            {
                k = w;
                min = D[w];
            }
        }

        final[k] = 1;                                           //距离顶点k的最近距离已经找到

        for (int w = 0; w < G.numVertexes; w++)                 //更新最短路径及距离
        {
            if (!final[w] && (G.arc[k][w] + min) < D[w])        //如果找到了更短路径，且顶点k可以到达w顶点
            {
                D[w] = min + G.arc[k][w];                       //更新v0到w顶点的距离
                P[w] = k;                                       //v0到w的顶点的中间顶点为k，即更新v0顶点到w顶点的路径经过k
            }
        }
    }
}

//floyd算法
void ShortestPath_Floyd(MGraph G, Pathmatrix P, ShortPathTable_floyd D)
{
    //step1:初始化P、D
    for (int i = 0; i < G.numVertexes; i++)
    {
        for (int j = 0; j < G.numVertexes; j++)
        {
            D[i][j] = G.arc[i][j];

            P[i][j] = j;
        }
    }

    //step2:更新P、D
    for (int i = 0; i < G.numVertexes; i++)                 //每一个中转顶点加入后更新
    {
        for (int j = 0; j < G.numVertexes; j++)             //更新P、D
        {
            for (int k = 0; k < G.numVertexes; k++)
            {
                if (D[j][k] > D[j][i] + D[i][k])            //如果该顶点j到k的路径经过i中转后变小，则进行更新
                {
                    D[j][k] = D[j][i] + D[i][k];
                    P[j][k] = P[j][i];                      //记录j到k经过顶点i中转
                }
            }
        }
    }
}

main.cpp

#include <iostream>
#include "MGraph.h"
#include "ALGraph.h"
#include <stack>

using namespace std;

extern bool* visited, * visited1;

int main(int argc, char** argv)
{
    //1.邻接矩阵
    MGraph MG;
    CreateMGrah(MG);

    for (int i = 0; i < MG.numVertexes; i++)    //对于连通图，只执行一次
    {
        if (!visited[i])
        {
            DFS(MG, i);                         //深度优先搜索遍历
            //BFS(MG, 0);                       //广度优先搜索遍历
        }
    }

    cout << "\nPrim 最小生成树：" << endl;
    /*
    A D 1
    A E 3
    A B 7
    B C 5
    B E 2
    C D 6
    C E 8
    D E 4
    */
    MiniSpanTree_Prim(MG);

    cout << "\nKruskal 最小生成树：" << endl;
    //Edge edges[MAXEDGE] = { 0 };
    //MGraph2Edge(MG, edges);
    MiniSpanTree_Kruskal(MG);

    cout << "\nDijkstra算法求解最短路径：" << endl;

    Patharc P;
    ShortPathTable D;
    ShortestPath_Dijkstra(MG, 0, P, D);
    for (int i = 1; i < MG.numVertexes; i++)
    {
        //输出v0到每一个顶点的最短路径
        int p = P[i];                       //到第i个顶点的倒数第二个顶点
        stack<int> s;
        while (p)                           //寻找中间顶点
        {
            s.push(p);
            p = P[p];                       //下一个顶点
        }

        //输出路径
        cout << MG.vexs[0] << "->";
        while (!s.empty())
        {
            cout << MG.vexs[s.top()] << "->";
            s.pop();
        }
        cout << MG.vexs[i] << "  " << D[i] << endl;
    }

    cout << "\nFloyd算法求解最短路径：" << endl;
    Pathmatrix P_floyd;
    ShortPathTable_floyd D_floyd;
    ShortestPath_Floyd(MG, P_floyd, D_floyd);

    //输出每一个顶点与其他顶点之间的最短路径
    for (int i = 0; i < MG.numVertexes - 1; i++)                    //i为起点
    {
        for (int j = i + 1; j < MG.numVertexes; j++)            //j为终点
        {
            cout << MG.vexs[i] << "->";                         //输出源点
            int k = P_floyd[i][j];                              //中间顶点k
            while (k != j)                                      //直到终点
            {
                cout << MG.vexs[k] << "->";
                k = P_floyd[k][j];                              //继续找中间顶点
            }
            cout << MG.vexs[j];                                 //输出终点
            cout << "   " << D_floyd[i][j] << endl;
        }
    }
    return 0;
}