2021-06-04 从例题看Dijkstra算法

/背景/
在图论的学习中，非常有实用性的一个课题：最短路径。
这里讨论一下Dijkstra算法求最短路径。
**用于图中某一顶点到其余各顶点的最短路径。

/理论/
Dijkstra的主要思想是分两个集合存放结点。S集合存放已确定路径会经过的顶点，T集合存放暂时查到最短路径但还未确定的顶点。从出发点开始，每次遍历S集合最新节点的可达到节点路径，计算最短路径后存入T集合，最短路径到达的节点入S集合，直至所有节点遍历结束。这个算法的主要思想也可以用贪心算法来总结。每次获取下一段最短路径，上一段都已经是最短路径。

/实 现/

Dijkstra的实现主要使用三个辅助数组。

1. dist[]表示当前S最新节点至可到达节点的最短距离。不可直达的暂不计算。
2. path[]表示当前S最新节点最短路径的上一个节点。
3. set[]标记已入S集合的节点。

来看一道例题，了解下算法。

WX20210604-142221@2x.png

以顶点0为起点：

dist[1] = 4 < dist[2] = 6 < dist[3] = 6
dist[4] = dist[1] + dist[1][4] = 11
以1为中转点检测

	0	1	2	3	4	5	6
Dist	0	4	5	6	11	-	-
Path	-1	0	1	0	1	-1	-1
Set	1	1	0	0	0	0	0

dist[2] = 6 > dist[1] + dist[1][2] = 5
dist[3]=6 < dist[1] + dist[1][2] + dist[2][3] = 7 < dist[2] + dist[2]dist[3] = 8
dist[4] = dist[1]+dist[1][4] = 11 (以下省略遍历步骤，只给出最短路径)
dist[5] = dist[1] + dist[1][2] +dist[2][5] = 9
以2为中转点检测

	0	1	2	3	4	5	6
Dist	0	4	5	6	11	9	-
Path	-1	0	1	0	1	2	-1
Set	1	1	1	0	0	0	0

dist[4] = 11
dist[5] = 9
以3位中转点检测

	0	1	2	3	4	5	6
Dist	0	4	5	6	11	9	-
Path	-1	0	1	0	1	2	-1
Set	1	1	1	1	0	0	0

** dist[4] = dist[1] + dist[1][2] + dist[2][5] + dist[5][4] = 10 （注意：此处更新了4的路径）
** dist[6] = dist[1] + dist[1][2] + dist[2][5] + dist[5][6] = 17 (注意：此处4还未入S集合，所以最短路径只能走5)
以5为中转点检测（因为5比4路径短）

	0	1	2	3	4	5	6
Dist	0	4	5	6	10	9	17
Path	-1	0	1	0	1	2	5
Set	1	1	1	1	0	1	0

dist[5] = 9
dist[6] = dist[1] + dist[1][2] + dist[2][5] + dist[5][4] + dist[4][6] = 16
以4为中转点检测

	0	1	2	3	4	5	6
Dist	0	4	5	6	10	9	16
Path	-1	0	1	0	5	2	4
Set	1	1	1	1	1	1	0

所有节点并入

	0	1	2	3	4	5	6
Dist	0	4	5	6	10	9	16
Path	-1	0	1	0	5	2	4
Set	1	1	1	1	1	1	1

再来看一下实现代码：

// 图的定义 顺序存储
typedef struct
{
    int edges[maxSize][maxSize];
    // 邻接矩阵定义，如果是有权图，则在此句中将int改为float
    int n, e; // 分别为顶点数和边数
    VertextType vex[maxSize];
}MGraph;

// Dijkstra path数组。内容是一棵双亲存储结构的树。
void printfPath(int path[], int a)
{
    int stack[maxSize], top = -1;
    while (path[a] != -1)
    {
        stack[++top] = a;
        a = path[a];
    }
    stack[++top] = a;
    while (top != -1)
    {
        cout<<stack[top--]<<" "; 
    }
    cout<<endl;
    
}

//Dijkstra
void Dijkstra(MGraph g, int v, int dist[], int path[])
{
    int set[maxSize];
    int min, i, j, u;
    // 初始化各个数组
    for ( i = 0; i < g.n; ++i)
    {
        dist[i] = g.edges[v][i];
        set[i] = 0;
        if (g.edges[v][i] < INF)
        {
            path[i] = v;
        }
        else
        {
            path[i] = -1;
        }
        
    }
    set[v] = 1;
    path[v] = -1;
    // 初始化结束 开始关键操作
    for ( i = 0; i < g.n-1; ++i)
    {
       min = INF; // INF是一个常量 要比所有权值大 为了获得最小值
       for ( j = 0; j < g.n; ++j) // 每次从未入S集合的点中获取路径最短的点
       {
           if (set[j] == 0 && dist[j] < min)
           {
               u = j;
               min = dist[j];
           }
           
       }
       set[u] = 1; // 入S集合
       
       for ( j = 0; j < g.n; ++j)
       {
           if (set[j]==0 && dist[u] + g.edges[u][j] < dist[j]) // 如果有更短的路径 进行更新
           {
               dist[j] = dist[u] + g.edges[u][j];
               path[j] = u;
           }
           
       }
       
    }
    
}

有时候看文字看不懂，可以考虑做题试试，也许迎刃而解 :P