图解：最短路径之迪杰斯特拉算法-蒲公英云

点击关注上方“五分钟学算法”，

设为“置顶或星标”，第一时间送达干货。

format_png

转自景禹

今天我们主要看一个最短路径算法，迪杰斯特拉算法（Dijkstra Algorithm）（ 计算从某个源点到其他顶点的最短路径的算法 ）。

小禹禹： 景禹，什么是最短路径，什么又是源点，还有最短路径算法有啥子用呢？

景禹： 小禹禹一下子提出这么多疑问，我们一个一个来看看吧~~

基础概念

什么是源点？

路径起始的第一个顶点称为源点（Source），最后一个顶点称为终点（Destination）。图下图中，我们用红色标注出的就可以认为是一个路径（）的源点和终点，但不要有误区，其实图中的任何一个顶点都可作为源点或者终点，源点与终点只是相对一条路径而言的。

format_png 1

什么是最短路径？

对于无向图而言，从源点到终点的最短路径就是从源点到终点所包含的边最少的路径。我们只需要从源点出发对图做广度优先搜索，一旦遇到终点就终止。我们可以具体来看看如何得到无向图中源点到终点的最短路径。

第一步：遍历顶点：

format_png 2

第二步：遍历顶点的邻接顶点和（具体操作中我们使用队列来进行实现）：

format_png 3

第三步：遍历顶点的邻接顶点和，遍历顶点的邻接顶点：

format_png 4

第四步：遍历顶点的邻接顶点和的邻接顶点：

format_png 5

第五步：遍历顶点的邻接顶点，发现正好是终点（Destination）：

format_png 6

由此可以得到，图中从源点到终点的（第一条）一条最短路径（）：

format_png 7

最短路径的用处有哪些？

简单来说，我们要从大兴机场到北京天安门，如何规划路线才能换乘最少，并且耗时最少呢？这时候，最短路径算法就派上用场了，你每天使用的导航系统进行道路规划也同样依赖于底层的算法！虽然现实情况可能更复杂一些，但是学习最基础的算法对于我们日后的提升总有莫大的帮助。我们接着看今天的主角：迪杰斯特拉算法。

format_png 8

迪杰斯特拉算法

迪杰斯特拉算法是一个单源点最短路径算法，即该算法会求得从指定一个顶点（源点）到其余所有顶点的最短路径。

首先，引进一个辅助向量D，它的每一个分量表示当前所找到的从源点到每一个顶点的最短路径的长度。它的初态为：若从到有弧（边），则为弧上的权值；否则为无穷（INF）。显然，长度为

的路径就是从出发的长度最短的一条最短路径。此路径为。

小禹禹：这都是什么呀，看不懂？？？

景禹： 那我们就直接看栗子吧，看完你绝对懂！

format_png 9

我们以上图为例来演示迪杰斯特拉算法的详细执行过程。

第一步：初始化辅助向量D，路径向量P 和当前已求得顶点到的最短路径的向量Final。

format_png 10

辅助向量D的初态为：若从到有弧，则为弧上的权值；否则为无穷（INF）。对应到图中，到有弧，则；到有弧，则；到其他顶点没有弧，则相应的用无穷（INF）表示。路径向量P用于存储最短路径下标的数组，初始时全部置为零；向量Final中值为1表示顶点到的最短路径已求得，到的最短路径当然是已求得，所以将设置为1。接下来就是迪杰斯特拉算法的核心了，认真看奥。

第二步：遍历源点, 找到源点的邻接顶点中距离最短的顶点，即，到的最短路径为1已经求出，更新.

format_png 11

第三步：遍历顶点，找到顶点的邻接顶点、、、（其中已经遍历过了，不需要考虑）。从到的距离是 3，所以到的距离是 1+3=4，小于辅助向量D中的距离 5，则更新；从到的距离是 3，所以到的距离是 1+7=8，小于辅助向量中的，则更新；从到的距离是 5，所以到的距离是 1+5=6，小于辅助向量中的，则更新；相应的将顶点、、的前驱结点更新为的下标 1。

format_png 12

接下来就是重复第二步、第三步。

第四步：遍历源点, 找到从源点出发距离最短的且final=0的顶点，发现为, 更新.

format_png 13

第五步：遍历顶点并更新辅助向量 D 和路径向量 P 。

format_png 14

第六步：找到从源点出发距离最短的且final=0的顶点，发现为, 更新.

format_png 15

第七步：遍历顶点并更新辅助向量 D 和路径向量 P 。

format_png 16

第八步：找到从源点出发距离最短的且final=0的顶点，发现为, 更新.

format_png 17

第九步：遍历顶点并更新辅助向量 D 和路径向量 P 。

format_png 18

第十步：找到从源点出发距离最短的且final=0的顶点，发现为, 更新.

format_png 19

第十一步：遍历顶点并更新辅助向量 D 和路径向量 P 。

format_png 20

第十二步：找到从源点出发距离最短的且final=0的顶点，发现为, 更新.

format_png 21

第十三步：遍历顶点并更新辅助向量 D 和路径向量 P 。

format_png 22

第十四步：找到从源点出发距离最短的且final=0的顶点，发现为, 更新.

format_png 23

第十三步：遍历顶点并更新辅助向量 D 和路径向量 P 。

format_png 24

第十二步：找到从源点出发距离最短的且final=0的顶点，发现为, 更新。整个迪杰斯特拉算法终止。

format_png 25

根据路径向量我们则可以得到从源点到终点的最短路径，即图中红色线所标注的路径。

format_png 26

按照上面的思路，我们来看下面的代码将觉得豁然开朗了。

#define MAXVEX 9
#define  INFINITY 65535
typedef  int  Patharc[MAXVEX]; // 用于存储最短路径下标的数组
typedef int  ShortPathTable[MAXVEX]; // 用于存储到各点最短路径的权值和
void ShortestPath_Dijkstar(MGraph G, int V0, Patharc *P, ShortPathTable *D)
{
  int v, w, k, min;
  int final[MAXVEX]; // final[w] = 1 表示已经求得顶点V0到Vw的最短路径
  // 初始化数据
  for( v=0; v < G.numVertexes; v++ )
  {
    final[v] = 0; // 全部顶点初始化为未找到最短路径
    (*D)[V] = G.arc[V0][v]; // 将与V0点有连线的顶点加上权值
    (*P)[V] = 0; // 初始化路径数组P为0
  }
  (*D)[V0] = 0; // V0至V0的路径为0
  final[V0] = 1; // V0至V0不需要求路径
  // 开始主循环，每次求得V0到某个V顶点的最短路径
  for( v=1; v < G.numVertexes; v++ )
  {
    min = INFINITY;
    for( w=0; w < G.numVertexes; w++ )
    {
      if( !final[w] && (*D)[w]<min )
      {
        k = w;
        min = (*D)[w];
      }
    }
    final[k] = 1; // 将目前找到的最近的顶点置1
    // 修正当前最短路径及距离
    for( w=0; w < G.numVextexes; w++ )
    {
      // 如果经过v顶点的路径比现在这条路径的长度短的话，更新！
      if( !final[w] && (min+G.arc[k][w] < (*D)[w]) )
      {
        (*D)[w] = min + G.arc[k][w]; // 修改当前路径长度
        (*p)[w] = k; // 存放前驱顶点
      }
    }
  }
}

时间复杂度分析

初始化辅助向量 D 和路径向量 P，以及final数组的时间复杂度为.

迪杰斯特拉算法的核心代码中，外层for循环从 1 遍历到 n-1，执行了n-1次，内层的两个for循环分别从0 遍历到 n-1，分别执行了n次，共执行了2n次；外层循环执行一次，内层循环执行2n次，则总的执行次数为(n-1)*2n，所以迪杰斯特拉算法的时间复杂度为.

细心的朋友肯定发现，我们在辅助向量D中查找从源顶点到最短路径未知顶点最短距离（也就是final=0的顶点）的顶点时，时间复杂度，更新选择出的顶点的邻接顶点时（内层循环的第二for循环）也耗时。因此我们在实现上可以使用小顶堆数据结构进行优化，这样就可以将时间复杂度降到。

迪杰斯特拉算法（堆优化）

要使用堆数据结构对迪杰斯特拉算法进行优化，我们可以直接使用C++的STL 中的 priority_queue 进行实现，注意我们下方的实现采用的是邻接表的存储结构（大家可以直接复制DeBug调试）：

#include<bits/stdc++.h>
using namespace std;
# define INF 0x3f3f3f3f
typedef pair<int, int> iPair;
class Graph
{
    int V; // 顶点个数
    //带权图中需要保存顶点的权值。
    list< pair<int, int> > *adj;
public:
    Graph(int V); // 构造器
    // 添加边和权值
    void addEdge(int u, int v, int w);
    // 打印源点s到其他顶点的最短路径
    void shortestPath(int s);
};
// 为邻接表分配空间
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<iPair> [V];
}
void Graph::addEdge(int u, int v, int w)
{
    adj[u].push_back(make_pair(v, w));
    adj[v].push_back(make_pair(u, w));
}
// 打印从源顶点到其他顶点的最短路径
void Graph::shortestPath(int src)
{
    // 创建一个优先队列实现小顶堆
    priority_queue< iPair, vector <iPair> , greater<iPair> > pq;
    // 创建一个距离向量，初始化为INF
    vector<int> dist(V, INF);
    // 将源顶点入堆，并将到自身的距离初始化为0
    pq.push(make_pair(0, src));
    dist[src] = 0;
    /*循环直到堆为空*/
    while (!pq.empty())
    {
        // 取出堆顶的顶点并保存在 u中
        int u = pq.top().second;
        pq.pop();
        // 设置迭代器，遍历顶点 u 的所有邻接顶点。
        list< pair<int, int> >::iterator i;
        for (i = adj[u].begin(); i != adj[u].end(); ++i)
        {
            // 获取邻接顶点的标签和权值，即weight（u，v）
            int v = (*i).first;
            int weight = (*i).second;
            // 如果从u到v存在一条最短路径且当前顶点u的最短距离+weight(u,v)dist[v]的值，则更新
            if (dist[v] > dist[u] + weight)
            {
                dist[v] = dist[u] + weight;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
    // 打印最短路径
    printf("Vertex Distance from Source\n");
    for (int i = 0; i < V; ++i)
        printf("%d \t\t %d\n", i, dist[i]);
}
int main()
{
    int V = 9;
    Graph g(V);
    g.addEdge(0, 1, 1);
    g.addEdge(0, 2, 5);
    g.addEdge(1, 2, 3);
    g.addEdge(1, 4, 5);
    g.addEdge(1, 3, 7);
    g.addEdge(2, 4, 1);
    g.addEdge(2, 5, 7);
    g.addEdge(3, 4, 2);
    g.addEdge(3, 6, 3);
    g.addEdge(4, 5, 3);
    g.addEdge(4, 6, 6);
    g.addEdge(4, 7, 9);
    g.addEdge(5, 7, 5);
    g.addEdge(6, 7, 2);
    g.addEdge(6, 8, 7);
    g.addEdge(7, 8, 4);
    g.shortestPath(0);
    return 0;
}

总结

最短路径问题在日常生活中很普遍，今日主要讨论了迪杰斯特拉算法，一种计算从指定顶点到其他所有顶点的最短路径算法。实现方式上，我们可以采用最原始的思想进行实现，此外可以采用小顶堆进行优化，从而降低时间复杂度。但是有一个问题，我们如何计算 任意两点间的最短路径 呢？因为迪杰斯特拉算法仅仅只能计算从一个顶点到其他顶点的最短路径。待景禹改日再给你们道来。