最短路径的Dijksatra算法.

Dijkstra算法是一种用于计算图中最短路径的贪心算法。它的基本思想是从起点开始，逐步扩展到尚未处理的节点，直到到达目标节点为止。这个过程中，我们会记录到达每个节点的最短路径，并且只对未处理的节点进行扩展。Dijkstra算法使用了一个优先队列来存储待处理的节点，并按照从起点到该节点的最短距离排序。

下面是Dijkstra算法的伪代码：

function Dijkstra(Graph, source):
    dist[source] := 0                     // 到源点的距离为0
    create vertex set Q                   // 创建一个顶点集合Q
    for each vertex v in Graph:            // 对于图中的每个顶点
        if v ≠ source:
            dist[v] := infinity           // 到源点的距离为无穷大
        prev[v] := undefined              // 前驱节点为未定义
        Q.add_with_priority(v, dist[v])    // 将顶点v加入Q中，并按照dist[v]值排序

    while Q is not empty:                  // 当Q不为空时
        u := Q.extract_min()               // 从Q中提取具有最小dist[u]值的顶点u
        for each neighbor v of u:          // 对于u的每个邻居v
            alt := dist[u] + length(u, v) // 计算到v的新距离
            if alt < dist[v]:              // 如果新距离更短
                dist[v] := alt            // 更新dist[v]值
                prev[v] := u              // 更新前驱节点
                Q.decrease_priority(v, alt) // 重新排序Q中的顶点v

    return dist, prev                      // 返回最短距离和前驱节点

其中，Graph表示我们要计算最短路径的图，source表示起点。dist和prev数组分别记录每个节点的最短距离和前驱节点。Q是一个优先队列，用于存储待处理的节点。在每次循环中，我们会从Q中提取距离起点最近的节点u，并遍历u的所有邻居节点v。如果到v的距离比之前记录的距离更短，我们就更新最短距离和前驱节点，并且重新排序Q中的节点。

Dijkstra算法的时间复杂度为O(E log V)，其中E是边的数量，V是节点的数量。它在稠密图中表现优秀，但在稀疏图中会比较慢。此外，Dijkstra算法只适用于无负权边的图。如果图中存在负权边，需要使用Bellman-Ford算法或者SPFA算法。