東京大学 新領域創成科学研究科 メディカル情報生命専攻 2016年8月実施 問題10

Author

zephyr

Description

We define the shortest distance from a vertex to a vertex on a graph as the number of edges in a path from to that contains the smallest number of edges, except that the shortest distance is when no such path exists and that it is when and are identical.

(1) Let us consider the directed graph shown below.

• (A) Show the adjacency matrix.
• (B) Show a matrix , whose element is the shortest distance from a vertex to a vertex .

(2) Suppose we are given a simple directed graph , where the vertex set and is the edge set. is represented by a matrix , where

• (A) Let . Let be the set of edges in that start from and end at a vertex in . Let be the shortest distance from a vertex to a vertex on a directed graph , and let . Express in terms of .

• (B) can be computed from as follows. Fill in the two blanks.

• (C) Given , show an algorithm to compute the all-pair shortest distances, and find its time complexity with regard to .

---

我们将从顶点 到顶点 的最短距离定义为图中从 到 的包含最少边数的路径中的边数，除了当不存在这样的路径时最短距离为 ，以及当 和 相同时为 。

(1) 让我们考虑下图所示的有向图。

• (A) 显示邻接矩阵。
• (B) 显示一个矩阵 ，其元素 是从顶点 到顶点 的最短距离。

(2) 假设我们有一个简单的有向图 ，其中顶点集 和边集 。 由矩阵 表示，其中

• (A) 设 。设 为从顶点 中的顶点出发并结束于顶点的边集。设 为有向图 上从顶点 到顶点 的最短距离，并设 。用 表示 。
• (B) 可以从 计算如下。填写两个空格。

• (C) 给定 ，展示一个算法来计算所有对的最短距离，并找到其关于 的时间复杂度。

Kai

(1)

(A)

The adjacency matrix for the graph is a square matrix where the element is 1 if there is an edge from vertex to vertex , and 0 otherwise.

(B)

The matrix will be computed using the Floyd-Warshall algorithm. The element is the shortest distance from vertex to vertex .

1. Initialize with:

   • if
   • if there is an edge from to
   • otherwise

2. Update using the Floyd-Warshall algorithm:

The final matrix is:

(2)

(A)

The matrix is computed by considering paths that may pass through the vertex 1.

(B)

To find from , use:

(C)

The Floyd-Warshall algorithm is suitable for computing all-pair shortest distances:

1. Initialize where is 0 if , 1 if there is an edge , and otherwise.
2. Update using: for all vertices from 1 to .

Algorithm:

function FloydWarshall(V, E):
    let D be a |V| x |V| matrix of minimum distances
    for each vertex v in V:
        D[v][v] = 0
    for each edge (u, v) in E:
        D[u][v] = 1
    for each k from 1 to |V|:
        for each i from 1 to |V|:
            for each j from 1 to |V|:
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    return D

Time Complexity:

The time complexity of the Floyd-Warshall algorithm is because it involves three nested loops, each running times.

Knowledge

最短路径 Floyd-Warshall算法 图论

重点词汇

• adjacency matrix 邻接矩阵
• shortest distance 最短距离
• edge 边
• vertex 顶点

参考资料

1. 《算法导论》 第 25 章 最短路径算法