图的最短路径

Dijkstra

主要思想

Dijkstra算法用于计算图中一点到其它点的最短路径。

每次从剩余顶点中找到离源点最近的点，将这个点加入已确定最短路径的点集，然后更新其他未确定最短路径并且与这个点相邻的点到源点的最短距离。

与Prim算法比较

相同点：

• 计算过程类似于Prim算法，都是从一个顶点开始，逐步向外扩展。

不同点：

• Prim算法是根据剩余顶点与生成树之间的距离最小来选取下一个点，而Dijkstra算法是根据剩余顶点与源点之间的距离最小。
• Prim算法每次加入一点后就对所有剩余的点进行更新，而Dijkstra算法只对未确定最短路并且与刚刚确定的点相邻的点进行更新。

代码

/// <summary>
/// 用Dijkstra算法确定源点到其余点的最短路径
/// </summary>
/// <param name="n">图的顶点数</param>
/// <param name="M">图的邻接矩阵</param>
/// <param name="v0">源点</param>
/// <param name="dist">各点到源点的最短距离</param>
/// <param name="path">最短路径上的一点</param>
void Dijkstra(int n, float** M, int v0, float dist[], int path[])
{
    bool* set = new bool[n];  // 是否以确定最短路径
    int v;                    // 当前确定最短路径的点
    for (int i = 0; i < n; i++) {
        dist[i] = M[v0][i];
        set[i] = false;
        if (M[v0][i] < INF) {
            path[i] = v0;     // 直接与v0相邻，初始路径上一点就是v0
        }
        else {
            path[i] = -1;     // （暂时）无路径
        }
    }
    set[v0] = true;
    path[v0] = -1;
    for (int i = 0; i < n - 1; i++) {  // 逐个确定剩余的n-1个点
        float min = INF;                 // 剩余点到源点的最小距离
        for (int j = 0; j < n; j++) {
            if (!set[i] && dist[j] < min) {
                v = j;
                min = dist[j];
            }
        }
        set[v] = true;                  // 确定最短路径
        for (int j = 0; j < n; j++) {                     // 更新剩余点到源点的最短距离
            if (!set[j] && dist[v] + M[v][j] < dist[j]) { // 通过刚刚确定的点v可以减少到源点的距离
                dist[j] = dist[v] + M[v][j];
                path[j] = v;
            }
        }
    }
}

输出路径

最后得到的path[v]保存的是v到源点的最短路径上的前一点u，比如：

graph LR
	v0((v0)) --> other((...)) --> u((u)) --> v((v))

对于源点v0，有path[v0]=-1

于是通过这个path[]数组就可以递归地得到最短路径上的所有点：

void PrintPath(int path[], int v)
{
    if (path[v] == -1) {
        printf("%d ", v);
    }
    else {
        PrintPath(path, path[v]);
        printf("-> %d ", v);
    }
}

Floyd

主要思想

Floyd算法用于计算图中所有点对之间的最短路径。

对于每个点v，尝试加入到所有点对(i, j)之间的路径上。如果从i到j的路径上加入顶点v之后路径变短，也就是 \(A[i][v] + A[v][j] < A[i][j]\)，其中A[][]数组保存的是当前所有点对之间最短路径的长度。

代码

void Floyd(int n, float** M, int** path)
{
    std::vector<std::vector<int>> A(n, std::vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            A[i][j] = M[i][j];
            path[i][j] = -1;  // 没有中间点（直接相连）
        }
    }
    for (int v = 0; v < n; v++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (A[i][v] + A[v][j] < A[i][j]) {
                    A[i][j] = A[i][v] + A[v][j];
                    path[i][j] = v;
                }
            }
        }
    }
}

输出路径

最后得到的path[][]保存的是点对之间路径上的一点，类似Dijkstra算法得到的结果，可以递归输出。

void PrintPath(int** path, int n, int u, int v)
{
    if (path[u][v] == -1) {
        printf("%d -> %d ",  u, v);
    }
    else {
        int mid = path[u][v];
        PrintPath(path, n, u, mid);
        PrintPath(path, n, mid, v);
    }
}