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.
    for i = 1 to G.V - 1:
        for each edge (u,v) in G.E: //Relax each edge V-1 times
    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

    for each vertex v in G.V:
        v.d = infinity
        v.previous = NIL
    s.d = 0

    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).
    topologically sort the vertices of G
    for each vertex u, taken in topologically sorted order:
        for each vertex v in G.Adj[u]:
  • Running time: O(V+E)
  1. Dijkstra algorithm: for directed graph with non-negative weight edge.
    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]:
  • 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: Logo

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s