Design an algorithm for the single source shortest

问题:

Suppose we are given a directed graph G = (V, E) with potentially positive and negative edge lengths, but no negative cycles. Let s ∈ V be a given source vertex. How to design an algorithm for the single-source shortest path problem that runs in time O(k(|V | + |E|)) if the shortest paths from s to any other vertex takes at most k edges?

回答1:

Here`s O(k(|V | + |E|)) approach:

1. We can use Bellman-Ford algorithm with some modifications
2. Create array D[] to store shortest path from node s to some node u
3. initially D[s]=0, and all other D[i]=+oo (infinity)
4. Now after we iterate throught all edges k times and relax them, D[u] holds shortest path value from node s to u after <=k edges

5. Because any s-u shortest path is atmost k edges, we can end algorithm after k iterations over edges

   Pseudocode:

   for each vertex v in vertices:
   D[v] := +oo

   D[s] = 0

   repeat k times:
   for each edge (u, v) with weight w in edges:
   if D[u] + w < D[v]:
   D[v] = D[u] + w