algorithm - 如何找到无向图中从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 存在唯一的最短路径>.

这是最终代码:

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}
    num_path = {vertex: 0 for vertex in self.vertices}
    dist[source] = 0
    num_path[source] = 1
    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[v] = num_path[u]
            elif alt == dist[v]:
                num_path[v] += 1

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