如何找出无向图中从s(任何起始顶点)到v(任何顶点)的最短路径是否唯一？

Question

给定无向图G =(V,E),没有负权重.检查给定图中每个顶点的最短路径唯一性的复杂性是多少？

Answer 1

您也可以轻松修改最短路径算法以查找最短路径的数量。例如考虑这个 Dijkstra 代码：

def dijkstra(self, source, dest):
    assert source in self.vertices
    dist = {vertex: inf for vertex in self.vertices}
    previous = {vertex: None for vertex in self.vertices}
    dist[source] = 0
    q = self.vertices.copy()
    neighbours = {vertex: set() for vertex in self.vertices}
    for start, end, cost in self.edges:
        neighbours[start].add((end, cost))

    while q:
        u = min(q, key=lambda vertex: dist[vertex])
        q.remove(u)
        if dist[u] == inf or u == dest:
            break
        for v, cost in neighbours[u]:
            alt = dist[u] + cost
            if alt < dist[v]:                                  # Relax (u,v,a)
                dist[v] = alt
                previous[v] = u

我们添加另一个列表来存储到每个节点的最短路径的数量。

num_path = {vertex: 0 for vertex in self.vertices}

然后在松弛阶段，不是检查新距离（alt）是否小于先前的距离，而是检查它是否也相等。如果相等，我们增加该节点的最短路径数：

if alt == dist[v]:
    num_path[v] += 1

当我们为一个节点找到一个新的最短路径时，新节点的最短路径数等于其父节点的最短路径数：

if alt < distance:
    num_path[v] = num_path[u]
    ...

所以最后如果num_path[v]==1那么我们可以得出结论，从source到存在唯一的最短路径v。

这是最终的代码：

num_path = {vertex: 0 for vertex in self.vertices}

所以复杂度将等于你的最短路径算法的复杂度。