如何确定在无向图中从任意起点s到任意顶点v的最短路径是否唯一？

Question

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

- Sanket Achari

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

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

- Saeid

---

如果我们找到了一个从顶点到其邻居的路径，其长度等于估计的最短路径距离，那么最短路径数量将是该顶点的最短路径数量加上邻居的最短路径数量。代码中对应的语句为：elif alt == dist[v]: num_path[v] += num_path[u] - Parag Verma