CODEWITHSUNDEEP
algorithmgraphgraph-algorithmdirected-graph
jjangjjangmanboongboong
jjangjjangmanboongboong

Reputation: 31

Design an algorithm for the single source shortest path problem that runs in time O(k(|V|+|E|))

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?

Upvotes: 3

Views: 424

Answers (1)

Photon
Photon

Reputation: 2777

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

Upvotes: 1

Related Questions