单源最短路径问题笔试举例

单源最短路径问题是指在一个加权有向图中，给定一个起点，找到从起点到图中其他所有顶点的最短路径。这个问题可以采用 Dijkstra 算法或者 Bellman-Ford 算法来解决。

以下是一个关于单源最短路径问题的笔试题例子：

假设有如下的加权有向图，其中顶点 1 到顶点 6 的编号依次为 1, 2, 3, 4, 5, 6，权重表示在两个顶点之间移动的代价：

        2
   (1)------>(2)
   / \         |
 3/   \1      |2
 /     \      |
v       v     v
(3)---->(4)-->(5)
 \      /1    |1
 4\   /      | 
   v v       v
   (6)------>(7)
        3

请使用 Dijkstra 算法求解顶点 1 到其他所有顶点的最短路径。

解题思路：

1. 初始化起点到各个顶点的距离为无穷大，起点到自身的距离为 0。

    dist[1] = 0
    dist[2] = inf
    dist[3] = inf
    dist[4] = inf
    dist[5] = inf
    dist[6] = inf
    dist[7] = inf

2. 从起点开始，依次扩展距离最短的顶点。

    1. dist[2] = 2, prev[2] = 1
    2. dist[3] = 3, prev[3] = 1
    3. dist[4] = 4, prev[4] = 2
    4. dist[5] = 6, prev[5] = 4
    5. dist[6] = 7, prev[6] = 3
    6. dist[7] = 10, prev[7] = 5

3. 最短路径为 1 -> 2 -> 4 -> 5 -> 7，距离为 10。

因此，顶点 1 到其他所有顶点的最短路径分别为：

1 -> 2，距离为 2
1 -> 3，距离为 3
1 -> 4，距离为 4
1 -> 5，距离为 6
1 -> 6，距离为 7
1 -> 7，距离为 10