Dijkstra是用来求单源最短路径的。“单源”的意思就是说Dijkstra算法只能求一个顶点到其他点的最短距离而不能任意两点。对于Dijkstra算法而言，前提是它的前提条件是针对连通图，而且路径要有权值，并且权值不能为负数。

Dijkstra的核心思想是贪心算法，即保证每个阶段选取到的顶点到起始点的路径长度都是最短的。在这种情况下，只需要不断计算并更新选取的顶点到其“邻接顶点”的路径长度就可以了，这对于路径长度必然是递增的（无权或非负权）图来说每一步的最优解就是整体的最优解。然而，对于有负权的图来说，有可能导致一种情况的发生：

两点之间的最短路径不是直线，而是曲线，就像是虫洞一样

算法详解

1.算法开始时，将图中的所有顶点分为两组，一组为已知最短路径的顶点，一组为未知最短路径的顶点，
初始时所有顶点都属于未知最短路径的顶点，并标记每个顶点的路径长度为无穷大。

2.将起始点的路径长度设为 0。

3.每个阶段中，选取所有未知最短路径的顶点中路径长度最短的那一个，将其标记为已知最短路径的顶点，

4.然后计算该顶点到其邻接顶点中属于未知最短路径的顶点的路径长度，如果计算得到的路径长度比原有的长度短，就更新该邻接顶点的路径长度，并将该邻接顶点的前置节点设为选取的顶点。

5.不断执行 3 – 4 操作，直到未知最短路径的顶点数量为 0。

Dijkstra算法的伪码如下：

function Dijkstra(Graph, source):

    create vertex set Q                     // 未知最短路径的顶点集合

    for each vertex v in Graph:
        dist[v] ← INFINITY                  // 起始点到该顶点的最短路径长度
        prev[v] ← UNDEFINED                 // 最短路径中该顶点的前置顶点
        add v to Q                          // 初始时，所有节点都是未知最短路径的顶点

    dist[source] ← 0                        // 将起始点的路径长度设为 0

    while Q is not empty:
        u ← vertex in Q with min dist[u]    // 选取路径长度最短的一个

        remove u from Q 

        for each adjacent v of u:           // 遍历选取的顶点的邻接顶点
            alt ← dist[u] + length(u, v)
            if alt < dist[v]:               // 计算得到的路径比原有的小
                dist[v] ← alt 
                prev[v] ← u 

    return dist[], prev[]