6.5 最短路径与传递闭包

  • 『单源多目标最短路径』 已知有向图 G=(V,E)G = (V, E),权值函数 w(e)w(e) 和一个源点 v0v_0,且对于图 GG 中的所有边 ee,都有 w(e)>0w(e) > 0。希望找到从源点 v0v_0 出发到达图 GG 中所有其他顶点的最短路径。

引入 「Dijkstra 算法」,令 SS 表示已经找出最短路径的顶点集合,包括源点 v0v_0。令 distance[w] 表示从源点 v0v_0 出发,且只经过 SS 中的顶点,并最终到达 ww 的最短路径的长度。该算法从 v0v_0 开始,在 distance 中找到一个顶点 ii,使得 distance[i] 最小,则将顶点 ii 加入 SS,并更新 distance 检查其他顶点在 v0v_0 经过 ii 时是否有更小的 distance 值。直到找出 v0v_0 到所有顶点的最短距离。

在算法实现里,用数组 found 来表示集合 SS。如果顶点 ii 不在 SS 中,则 found[i] = false,反之为 true。用代价邻接矩阵 cost 来表示图 GGcost[i][j] 的值表示边 <i,j><i, j> 上的权值。如果 <i,j><i, j> 不是图 GG 的边,则 cost[i][j] 就取一个充分大的数。但此数必须保证语句 distance[u] + cost[u][w] 不会产生符号为溢出。该算法采用代价邻接矩阵来表示图,时间复杂度为 O(n2)O(n^2)

void shortestpath(int v, int cost[][MAX_VERTICES], int distance[], int n, short int found[])
{
    int i, u, w;
    for (i = 0; i < n; i++) {
        found[i] = false;
        distance[i] = cost[v][i];
    }
    found[v] = true;
    distance[v] = 0;
    for (i = 0; i < n-2; i++) {
        u = choose(distance, n, found);
        found[u] = true;
        for (w = 0; w < n; w++)
            if (!found[w])
                if (distance[u] + cost[u][w] < distance[w])
                    distance[w] = distance[u] + cost[u][w];
    }
}

int choose(int distance[], int n, short int found[])
{
    int i, min, minpos;
    min = INT_MAX;
    minpos = -1;
    for (i = 0; i < n; i++)
        if (distance[i] < min && !found[i])
        {
            min = distance[i];
            minpos = i;
        }
    return minpos;
}
  • 『所有顶点对之间的最短路径』 如果需要找出图中所有顶点对之间的最短路径,可以分别以每个顶点作为源顶点,使用上述算法即可。时间复杂度为 O(n3)O(n^3)。不过也可以考虑如下更为简单的算法,即使它的时间复杂度也为 O(n3)O(n^3)

Ak[i][j]A^k[i][j] 表示从顶点 ii 出发,只经过序号小于等于 kk 的中间顶点,到达顶点 jj 的最短路径代价。若用 cost[i][j]cost[i][j] 表示 <i,j><i,j> 上的权值,那么:

  1. 顶点 ii 到顶点 jj 的最短路径代价等于 An1[i][j]A^{n-1}[i][j]
  2. A1[i][j]=cost[i][j]A^{-1}[i][j] = cost[i][j],表示从 iijj 且不经过中间顶点的路径。
  3. Ak[i][j]A^{k}[i][j] 不经过顶点 kk,则其等于 Ak1[i][j]A^{k-1}[i][j]
  4. Ak[i][j]A^{k}[i][j] 经过顶点 kk,则其等于 Ak1[i][k]+Ak1[k][j]A^{k-1}[i][k] + A^{k-1}[k][j]

所以 Ak[i][k]=min{Ak1[i][j],Ak1[i][k]+Ak1[k][j]},k0A^k[i][k] = \min\{A^{k-1}[i][j], A^{k-1}[i][k] + A^{k-1}[k][j]\}, k \geq 0

函数 allcosts 来计算 An1[i][j]A^{n-1}[i][j]

void allcosts(int cost[][MAX_VERTICES], int distance[][MAX_VERTICES], int n)
{
    int i, j, k;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            distance[i][j] = cost[i][j];
    for (k = 0; k < n; k++)
        for (i = 0; i < n; i++)
            for (j = 0; j < n; j++)
                if (distance[i][k] + distance[k][j] < distance[i][j])
                    distance[i][j] = distance[i][k] + distance[k][j];
}
  • 「传递闭包 transitive closure」GG 是一个边不带权值的有向图,图中的两个顶点之间存在路径,且路径上边的条数为正数。
  • 「自反传递闭包 reflexive transitive closure」GG 是一个边不带权值的有向图,图中的两个顶点之间存在路径,且路径上边的条数为非负数。
  • 「传递闭包矩阵 transitive closure matrix」 是一个矩阵,记作 A+A^+,如果从顶点 iijj 存在一条边数大于 0 的路径,则 A+[i][j]=1A^+[i][j] = 1,否则 A+[i][j]=0A^+[i][j] = 0
  • 「自反传递闭包矩阵 reflexive transitive closure matrix」 是一个矩阵,记作 AA^*,使得如果从顶点 iijj 存在一条长度大于等于 0 的路径,则 A[i][j]=0A^*[i][j] = 0

results matching ""

    No results matching ""