How to find whether the shortest path from s (any starting vertex) to v (any vertex) in the undirected graph is unique or not?

Question

Given an undirected graph G = (V, E) with no negative weights. What is the complexity for checking uniqueness of shortest path for every vertex in the given graph?

Answer 1

You can easily modify shortest path algorithms to find number of shortest paths too. For instance consider this Dijkstra code:

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

We add another list to store the number of shortest path to each node.

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

Then in the relaxing stage, instead of checking whether the new distance (alt) is less than previous distance, we check if it is equal too. If it is equal we increment the number of shortest paths for that node:

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

When we find a new shortest for a node, the number of shortest path for the new node is equal to the number of shortest path of its parent:

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

So in the end if num_path[v]==1 then we can conclude that there is a unique shortest path from source to v.

Here is the final code:

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

So the complexity will be equal to the complexity of your shortest path algorithm.