[数据结构与算法]Dijsktra算法解析

迪杰斯特拉算法(Dijkstra)是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

现在假设有下面这个带权无向图

此无向带权图的邻接矩阵如下：
PS：“∞” 意思是距离无限远也就是两个顶点间没有接触。

再假设从0点出发寻找去各个顶点的最短路径。
用vis记录顶点是否被访问，dis记录开始顶点到当前顶点的最短路径，prev记录当前顶点的前驱顶点。可以得到下面的表格。vis初始化为全部FALSE意思是任何一个顶点都没有被访问，dis被初始化为无穷远意思是假设开始顶点和任何一个顶点互相没有联系。前驱顶点初始化为-1。假设任何一个顶点没有前驱顶点。



PS：无向图中绿色代表已访问的顶点，蓝色代表未访问顶点。
我们开始的顶点是0。所以我们直接把顶点设为已访问。开始顶点是没有前驱顶点的所以不予理会。开始顶点到达自己的距离是0。接下来继续寻找开始顶点和其他顶点的连接情况。和顶点1的距离是7比无穷大要小所以更新dis[1]为7。因为当前的前驱顶点是0所以把prev[1]更新为0。继续寻找，开始顶点和顶点7的距离是5比无穷大要小所以更新dis[7]为5。因为当前的前驱顶点是0所以把prev[7]更新为0。开始顶点和其他顶点距离都是无限大所以其他数据暂时不变。从图找出未被访问的顶点中dis是最小值用该最小值对应的顶点做下一轮寻找的起始顶点。图中，绿色为已访问顶点，那么排除顶点0，剩下的顶点中顶点1的dis是7，顶点7的dis是5，其他的顶点的dis都是无穷大，所以不难看出顶点7是符合我们下一轮扫描的起始点。

顶点7是这一轮访问的起始点把顶点7标记为已访问。从顶点7出发分析顶点7到其他未被访问的顶点的连接情况。顶点7和未访问顶点1和6有联系。但是顶点7作为中间顶点到顶点1距离也就是开始顶点0经过顶点7到顶1的距离是5+11=16。16显然大于7所以dis[1]和prev[1]不做改变。顶点7作为中间顶点到顶点6距离也就是开始顶点0经过顶点7到顶6的距离是5+6=11。16显然小于无穷大所以dis[6]改成11和因为是从顶点7前往顶点6所以顶点6的前驱顶点为7也就是说prev[6]要改成7。继续从未访问节点找出dis最小的顶点开始进入我们下一轮搜索。图中不难看出符合条件的是顶点1。


也是老样子把顶点1标记为已访问。然后再分析顶点1到其他未访问顶点的联系。不难看出顶点1和顶点2和6有关系。顶点1作为中间节点到顶点2也就是从开始顶点0经过顶点1到达顶点2的距离为7+2=9。9显然小于无穷大所以dis[2]更新为9，是从顶点1前往顶点2的所以顶点2的前驱顶点为1因而prve[2]要更新为1。再看顶点6，顶点1作为中间节点到顶点6也就是从开始顶点0经过顶点1到达顶点6的距离为7+13=20。20要比11大也就是比dis[6]要大所以，dis[6]和prev[6]不进行更新。继续从未访问顶点找到dis最小的顶点，现在顶点2是符合条件的。下一轮搜索要从顶点2进行搜索。

老样子，首先标记顶点2为已访问顶点。然后再分析顶点2和其他为访问顶点的联系。从图中可知顶点2和顶点3和8有联系。顶点2作为中间顶点到顶点3也就是从开始顶点0经过顶点1再经过顶2到达顶点3的距离是7+2+4=13。13小于无限大所以dis[3]更新为13。因为要经过顶点2到达顶点3所以顶点3的前驱顶点为2也就是说prev[3]要更新为2。同理顶点2作为中间顶点到达顶点8的距离也就是开始顶点0经过顶点1再经过顶点2到达顶点8的距离为7+2+10=19。19小于无限大所以dis[8]更新为19。因为是从顶点2前往顶点8的所以顶点8的前驱顶点为2所以prev[8]更新为2。寻找下一个符合条件的搜索顶点，也就是在未访问顶点中dis最小的那个顶点。本次顶点6符合条件。下一轮搜索从顶点6开始。


当前访问搜索的顶点6所以把顶点6标记为已访问。再去分析顶点6和其他未访问顶点间的关系。图中可知顶点6和未被访问顶点5和8有联系。顶点6作为中间顶点到达顶点8也就是从开始顶点0经过顶点7再经过顶点6到达顶点8的距离是5+6+4=15。15小于19所以dis[8]改为15。因为当前情况是从顶点6前往顶点8的所以顶点8的前驱顶点改为顶点6。以此类推顶点6作为中间顶点到达顶点5的距离为5+6+14=25。25小于无限大所以dis[5]改为25前驱顶点prev[5]改为6。现在未访问顶点中dis最小的是顶点3。下一轮搜索用顶点3。

标记顶点3为已访问。分析顶点3和其他未被访问顶点的联系。图中不难看出顶点3和未访问顶点8，4，5都有联系。顶点3作为中间顶点到达顶点4的距离是7+2+4+9=22。22小于无穷大所以dis[4]更新为22前驱顶点prev[4]更新为3。顶点3作为中间顶点到达顶点5的距离是7+2+4+15=28。28大于25也就是大于dis[5]所以dis[5]和prev[5]不做改变。顶点3作为中间顶点到达顶点8的距离是7+2+4+6=19。19大于15也就是大于dis[8]所以dis[8]和prev[8]不做改变。准备进入下一轮扫描。当前未访问顶点中dis最小的是顶点8。下一轮扫描选择顶点8。


把顶点8标记为已访问。考虑顶点8与其他未访问顶点的关系是会发现顶点8和其他未访问顶点没有联系了。所以可以直接进入下一轮扫描。剩下的未访问顶点中dis最小的是顶点4。下一轮搜索用顶点4。


老样子标记4为已访问。然后再去分析和未访问顶点的联系。现在未访问顶点只有顶点5了顶点4作为中间顶点访问顶点5的话距离为7+2+4+9+3=25。25和25是相等的也就是说和顶点5的dis[5]相等所以dis[5]和prev[5]不进行更新。进入下一层扫描。现在未访问顶点就只剩下顶点5了理所当然下一轮搜索用顶点5。


顶点5也被标记为已访问了。已经没有其他未访问的顶点了。所以算法到此就结束了。最后我们就能获得dis和prev两个结果数组了。

下面是用C++代码实现Dijsktra算法

#include <iostream>

using namespace std;
//全局变量部分
const int MAXN = 1000;  //图的最大顶点数
const int INF = 1000000000; //设立INF为一个极大数，
            //这里这个数也可以设置为0x3f3f3f3f,这代表无穷大，即1061109567这一数值

int n;                  //当前图的点数
int vis[MAXN];          //标记数组用于记录图中各个点的被访问情况，0为未访问，1为已访问
int dis[MAXN];          //记录起点到各个顶点的最短路径长度
int prevNode[MAXN];         // 记录前驱顶点
int m[MAXN][MAXN] = 
{
    // 测试邻接矩阵
    //  {INF, INF, INF, INF, INF, INF, INF, INF, INF},
    {0,   7,   INF, INF, INF, INF, INF, 5,   INF},
    {7,   0,   2,   INF, INF, INF, 13,  11,  INF},
    {INF, 2,   0,   4,   INF, INF, INF, INF, 10},
    {INF, INF, 4,   0,   9,   15,  INF, INF, 6},
    {INF, INF, INF, 9,   0,   3,   INF, INF, INF},
    {INF, INF, INF, 15,  3,   0,   14,  INF, INF},
    {INF, 13,  INF, INF, INF, 14,  0,   6,   4},
    {5,   11,  INF, INF, INF, INF, 6,   0,   INF},
    {INF, INF, 10,  6,   INF, INF, 4,   INF, 0},
};      //用一个邻接矩阵来记录图中各个点的连接情况

void Dijkstra(int start) 
{   //start为起点
    fill(vis, vis + MAXN, 0); //将标记数组初始化为0即未被访问状态
    fill(dis, dis + MAXN, INF);   //将最短路数组初始化为一个很大的数
    fill(prevNode, prevNode + MAXN, -1); // 前驱顶点全部初始化为-1
    dis[start] = 0;           //首先将起点start到达自身的最短路设为0
    for (int i = 0; i < n; i++) 
    {   //n次循环，遍历完n个点   
        int node = -1;      //node记录当前能找到的从起点到此没被访问的最短的一个点
        int minn = INF;     //minn记录到达那个点的最短路径
        for (int j = 0; j < n; j++)    //每个点逐步寻找没被访问的最短的一个点
            if (vis[j] == 0 && dis[j] < minn) 
            {
                minn = dis[j];
                node = j;
            }

        if (node == -1)    //找不到小于INF的一个点，说明其他结点与定点不连通
            break;

        vis[node] = 1;  //将当前点标记为1
        for (int j = 0; j < n; j++)
            if (vis[j] == 0 && m[node][j] != INF && (dis[node] + m[node][j]) < dis[j])
            {
                //如果结点未被访问且 node能到达此结点 并且从起点到此结点过node中介点更近
                //在此标尺只有距离，如果有两条距离相等或多条相等，那么就只需在此进行修改
                //如路径相同第二标尺为花费时，则可通过在增加花费数组，在此if后加elseif判断距离相等情况花费不同条件。
                //下题就有两标尺。
                dis[j] = dis[node] + m[node][j];
                // 记录前驱顶点
                prevNode[j] = node;
            }
    }
}

int main()
{
    n = 9;              // 测试的邻接矩阵长度为9
    Dijkstra(0);        // 假设起始顶点为0
    cout << "start is 0\n\n";
    cout << "dis is :\n";
    for (int i = 0; i < n; i++)
        cout << "[" << i << "]:" << dis[i] << endl;
    cout << endl;
    cout << "prev is :\n";
    for (int i = 0; i < n; i++)
        cout << "[" << i << "]:" << prevNode[i] << endl;
    return 0;
}

测试的数据是我们上面分析的无向图。也是把开始顶点假设为0。程序输出结果如下：

和我们分析结果相同。到此Dijsktra算法就解析完毕了，感谢阅读。
下面是Dijsktra算法的应用题解析可以去尝试做一做
传送门：城市救援队Dijsktra算法应用题