Single Source Shortest Path

__BELLMAN-FORD
ALGORITHM:__

**Single Source Shortest Path**

**Problem**

Given a
directed graph *G(V,E)* with *weighted edges w(u,v)*, define the *path weight* of a path *p* as

For a
given source vertex *s*, find the *minimum weight paths* to every vertex
reachable from *s* denoted

The final
solution will satisfy certain caveats:

Â·
The graph cannot contain any *negative weight cycles* (otherwise there would be no minimum path
since we could simply continue to follow the negative weight cycle producing a
path weight of -âˆž).

Â·
The solution cannot have any *positive weight cycles* (since the cycle could simply be removed
giving a lower weight path).

Â· The solution can be assumed to have no zero weight cycles (since they would not affect the minimum value).

Therefore
given these caveats, we know the shortest paths must be *acyclic* (with â‰¤ |*V*|
distinct vertices) â‡’ â‰¤ |*V*| - 1 edges in each path.

**Generic Algorithm**

The
single source shortest path algorithms use the same notation as BFS with
predecessor Ï€ and distance *d* fields
for each vertex. The optimal solution will have *v.d* =

Î´(*s*,*v*)
for all *v* âˆˆ *V*.

The
solutions utilize the concept of *edge
relaxation* which is a test to determine whether going through edge (*u*,*v*)
reduces the distance to *v* and if so
update *v.*Ï€ and *v.d*. This is accomplished using the condition

**Bellman-Ford Algorithm**

The *Bellman-Ford algorithm* uses relaxation to
find single source shortest paths on directed graphs that may contain *negative weight edges*. The algorithm
will also detect if there are any *negative
weight cycles* (such that there is no solution).

**BELLMAN-FORD(G,w,s)**

1. INITIALIZE-SINGLE-SOURCE(G,s)

2. for i = 1
to |G.V|-1

3. for each edge (u,v) âˆˆ G.E

4. RELAX(u,v,w)

5. for
each edge (u,v) âˆˆ G.E

6.
if v.d > u.d + w(u,v)

7.
return FALSE

8. return
TRUE

**INITIALIZE-SINGLE-SOURCE(G,s)**

1. for
each vertex v âˆˆ G.V

2.
v.d = âˆž

3.
v.pi = NIL

4. s.d =
0

**RELAX(u,v,w)**

1. if v.d
> u.d + w(u,v)

2.
v.d = u.d + w(u,v)

3.
v.pi = u

Basically
the algorithm works as follows:

1. Initialize
*d*'s, Ï€'s, and set *s.d* = 0 â‡’ O(*V*)

2. Loop |*V*|-1 times through all edges checking
the relaxation condition to compute minimum distances â‡’ (|*V*|-1) O(*E*) = O(*VE*)

3. Loop
through all edges checking for negative weight cycles which occurs if any of
the relaxation conditions fail â‡’ O(*E*)

The run
time of the Bellman-Ford algorithm is O(*V*
+ *VE* + *E*) = O(*VE*).

Note that if the graph is a DAG (and thus is
known to not have any cycles), we can make Bellman-Ford more efficient by first
*topologically sorting G* (O(*V*+*E*)),
performing the same initialization (O(*V*)),
and then simply looping through each vertex *u
in topological* *order *relaxing
only the edges in Adj[*u*] (O(*E*)). This method only takes O(*V *+*
E*) time. This* *procedure (with a
few slight modifications) is useful for finding *critical paths* for PERT charts.

__Example:__

Given the
following directed graph

Using
vertex 5 as the source (setting its distance to 0), we initialize all the other
distances to âˆž.

*Iteration 1*: Edges (*u*_{5},*u*_{2})
and (*u*_{5},*u*_{4}) relax updating the
distances to 2 and 4

*Iteration 2*: Edges (*u*_{2},*u*_{1}),
(*u*_{4},*u*_{2}) and (*u*_{4},*u*_{3}) relax updating the
distances to 1, 2, and 4* *respectively.
Note edge (*u*_{4},*u*_{2}) finds a shorter path to
vertex 2 by going through vertex 4

*Iteration 3*: Edge (*u*_{2},*u*_{1})
relaxes (since a shorter path to vertex 2 was found in the previous* *iteration) updating the distance to 1

*Iteration 4*: No edges relax

The final
shortest paths from vertex 5 with corresponding distances is

*Negative cycle checks*: We now
check the relaxation condition one additional time for each* *edge. If any of the checks pass then there exists a negative
weight cycle in the graph.

*v*_{3}*.d *>* u*_{1}*.d *+* w*(1,3)* *â‡’* *4* *â‰¯* *6 + 6 = 12* *âœ“* *

*v*_{4}*.d *>* u*_{1}*.d *+* w*(1,4)* *â‡’* *2* *â‰¯* *6 + 3 = 9* *âœ“* *

*v*_{1}*.d *>* u*_{2}*.d *+* w*(2,1)* *â‡’* *6* *â‰¯* *3 + 3 = 6* *âœ“* *

*v*_{4}*.d *>* u*_{3}*.d *+* w*(3,4)* *â‡’* *2* *â‰¯* *3 + 2 = 5* *âœ“* *

*v*_{2}*.d *>* u*_{4}*.d *+* w*(4,2)* *â‡’* *3* *â‰¯* *2 + 1 = 3* *âœ“* *

*v*_{3}*.d *>* u*_{4}*.d *+* w*(4,3)* *â‡’* *3* *â‰¯* *2 + 1 = 3* *âœ“* *

*v*_{2}*.d *>* u*_{5}*.d *+* w*(5,2)* *â‡’* *3* *â‰¯* *0 + 4 = 4* *âœ“* *

*v*_{4}*.d *>* u*_{5}*.d *+* w*(5,4)* *â‡’* *2* *â‰¯* *0 + 2 = 2* *âœ“

Note that
for the edges *on the shortest paths*
the relaxation criteria gives equalities. Additionally, the path to any
reachable vertex can be found by starting at the vertex and following the Ï€'s
back to the source. For example, starting at vertex 1, *u*_{1}.Ï€ = 2, *u*_{2}.Ï€
= 4, *u*_{4}.Ï€

= 5 â‡’ the shortest path to vertex 1 is
{5,4,2,1}.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Programming and Data structures : Graphs : Bellman-Ford Algorithm |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright Â© 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.