Single Source Shortest Path

What is Single Source Shortest Path? Find the shortest paths from a source s to all other vertices v in graph G

  • First, we can argue that there is no negative, positive, or 0 weight cyclic path (cycle) in the shortest paths found. Therefore, the paths can contain at most V-1 edges.
  1. Bellman-Ford algorithm: the edge weight can be negative and there could be a negative cycle in the graph. If there is a negative cycle that can be reached from the source s, then it returns False. Otherwise, it returns True.
  • The algorithm is based on the fact that, for the path p = {v0,v1,v2,…,v_k} from source vertex v0 to v_k, if only (v0,v1), (v1,v2),…,(v_{k-1},v_k) are relaxed in such order, though mixed with other operations, then v_k.d will be the shortest distance from s to v_k.
Bellman-ford(G,w,s):
    Initialize-single-source(G,s)
    for i = 1 to G.V - 1:
        for each edge (u,v) in G.E: //Relax each edge V-1 times
            Relax(u,v,w)
    for each edge (u,v) in G.E: //to see if there is a negative cycle
        if v.d > u.d+w(u,v):
            return FALSE
    return TRUE

Initialize-single-source(G,s):
    for each vertex v in G.V:
        v.d = infinity
        v.previous = NIL
    s.d = 0

Relax(u,v,w):
    if v.d > u.d + w(u,v):
        v.d = u.d + w(u,v)
        v.previous = u
  • Running time: O(VE)
  1. Algorithm for directed acyclic graph (DAG).
DAG-shortest-paths(G,w,s):
    topologically sort the vertices of G
    Initialize-single-source(G,s)
    for each vertex u, taken in topologically sorted order:
        for each vertex v in G.Adj[u]:
            Relax(u,v,w)
  • Running time: O(V+E)
  1. Dijkstra algorithm: for directed graph with non-negative weight edge.
Dijkstra(G,w,s):
    Initialize-single-source(G,s)
    S = an empty set
    Q = G.V
    while Q is not empty:
        u = EXTRACT-MIN(Q)
        S = S.add(u)
        for each vertex v in G.Adj[u]:
            Relax(u,v,w)
  • Running time: similar to Prim algorithm.
    • Array: O(V^2);
    • binary heap: O(Vlg(V)+Elg(V));
    • Fibonacci heap: O(E+ Vlg(V)).

Sometimes, we can construct a artificial graph and use single source shortest path algorithms to solve the difference constraints problem. (The values of vertices satisfy some <= or >= relationship, which can be represented by the value of their edges.)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s