Floyd-Warshall Algorithm – All Pairs Shortest Paths

Floyd-Warshall Algorithm – All Pairs Shortest Paths

Floyd-Warshall Algorithm is an algorithm for finding the shortest path between all the pairs of vertices in a weighted graph. This algorithm works for both the directed and undirected weighted graphs. But, it does not work for the graphs with negative cycles.

Algorithm:

FLOYD - WARSHALL (W)

 1. n ← rows [W].

 2. D⁰ ← W

 3. for k ← 1 to n

 4. do for i ← 1 to n    

 5. do for j ← 1 to n    

 6. do d_ij^(k) ← min (d_ij^(k-1),d_ik^(k-1)+d_kj^(k-1) )

 7. return D⁽ⁿ⁾

Example:

Consider the above graph, to find all pairs shortest path build a n x n matrix. Here n is 4, therefore take a 4x4 matrix.

Initialize the weights to 0 to same nodes and all corresponding node weights.

Now for the three loop variables k,i,j iterate

In the above figure the rounded values are updated values in the loop iterations of k, i, j.

And the matrix gives all pairs shortest paths. 

Single-source shortest paths in directed acyclic graphs (DAG)

Single-source shortest paths in directed acyclic graphs (DAG)

Shortest paths are always well defined in a DAG, since even if there are negative-weight edges, no negative-weight cycles can exist.

The algorithm starts by topologically sorting the dag (see Topological sorting topic in blog) to impose a linear ordering on the vertices. If the dag contains a path from vertex u to vertex v, then u precedes v in the topological sort. We make just one pass over the vertices in the topologically sorted order.

As we process each vertex, we relax each edge that leaves the vertex.

The following theorem shows that the DAG-SHORTEST-PATHS procedure correctly computes the shortest paths.

The execution of the algorithm for shortest paths in a directed acyclic graph:

The vertices are topologically sorted from left to right. The source vertex is s. The d values appear within the vertices, and shaded edges indicate the  values.

Bellman–Ford single source shortest path algorithm

Bellman–Ford single source shortest path algorithm

Given a graph and a source vertex src in graph, find shortest paths from src to all vertices in the given graph. The graph may contain negative weight edges.

Following are the detailed steps.

Input: Graph and a source vertex src

Output: Shortest distance to all vertices from src. If there is a negative weight cycle, then shortest 

distances are not calculated, negative weight cycle is reported.

1) This step initializes distances from source to all vertices as infinite and distance to source itself as 0. Create an array dist[] of size |V| with all values as infinite except dist[src] where src is source vertex.

2) This step calculates shortest distances. Do following |V|-1 times where |V| is the number of vertices in given graph.

Do following for each edge u-v
             If dist[v] > dist[u] + weight of edge uv, then update dist[v]
             dist[v] = dist[u] + weight of edge uv

3) This step reports if there is a negative weight cycle in graph. Do following for each edge u-v
          If dist[v] > dist[u] + weight of edge uv, then “Graph contains negative weight cycle”

The idea of step 3 is, step 2 guarantees shortest distances if graph doesn’t contain negative weight cycle. If we iterate through all edges one more time and get a shorter path for any vertex, then there is a negative weight cycle

Example:

In this particular example, we have 5 vertices so there will be |V-1| that is 5-1= 4 passes. Each pass relaxes the edges in the order

Is the given graph with source node ‘s’ and initialized to 0 and all remaining distances initialized to infinity.

Start with all the ordered edges and start finding and updating distances

After Pass 4: there is no updating of distances after pass 4. It is the last pass and the shortest path is

Dijkstra’s single source shortest path algorithm

Dijkstra’s single source shortest path algorithm

Given a graph and a source vertex in the graph, find shortest paths from source to all vertices in the given graph.

Below are the detailed steps used in Dijkstra’s algorithm to find the shortest path from a single source vertex to all other vertices in the given graph.

Algorithm

1) Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest path tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty.

2) Assign a distance value to all vertices in the input graph. Initialize all distance values as 

INFINITE. Assign distance value as 0 for the source vertex so that it is picked first.

3) While sptSet doesn’t include all vertices

     a) Pick a vertex u which is not there in sptSet and has minimum distance value.
     b) Include u to sptSet.
     c) Update distance value of all adjacent vertices of u. To update the distance values, iterate           through all adjacent vertices. For every adjacent vertex v, if sum of distance value of u (from source) and weight of edge u-v, is less than the distance value of v, then update the distance value of v.

Let us consider the following example:

The set sptSet is initially empty and distances assigned to vertices are {0, INF, INF, INF, INF, INF, INF, INF} where INF indicates infinite.

The vertex 0 is picked, include it in sptSet. So sptSet becomes {0}. After including 0 to sptSet, update distance values of its adjacent vertices. Adjacent vertices of 0 are 1 and 7. The distance values of 1 and 7 are updated as 4 and 8.

Pick the vertex with minimum distance value and not already included in SPT (not in sptSET). The vertex 1 is picked and added to sptSet.

So sptSet now becomes {0, 1}. Update the distance values of adjacent vertices of 1.

Pick the vertex with minimum distance value and not already included in SPT (not in sptSET). Vertex 7 is picked. So sptSet now becomes {0, 1, 7}. Update the distance values of adjacent vertices of 7. 

Pick the vertex with minimum distance value and not already included in SPT (not in sptSET). Vertex 6 is picked. So sptSet now becomes {0, 1, 7, 6}. Update the distance values of adjacent vertices of 6. The distance value of vertex 5 and 8 are updated.

We repeat the above steps until sptSet does include all vertices of given graph. Finally, we get the following Shortest Path Tree (SPT).

Time Complexity of the implementation is O(V²). If the input graph is represented using adjacency list, it can be reduced to O(E log V) with the help of binary heap.

Dijkstra’s algorithm doesn’t work for graphs with negative weight edges. For graphs with negative weight edges, Bellman–Ford algorithm can be used.

Single Source Shortest Path Algorithms

Single Source Shortest Path Algorithms

In a shortest- paths problem, we are given a weighted, directed graphs G = (V, E), with weight function w: E → R mapping edges to real-valued weights. The weight of path p = (v₀,v₁,..... v_k) is the total of the weights of its constituent edges:

We define the shortest - path weight from u to v by δ(u,v) = min (w (p): u→v), if there is a path from u to v, and δ(u,v)= ∞, otherwise.

The shortest path from vertex s to vertex t is then defined as any path p with weight w (p) = δ(s,t).

The breadth-first- search algorithm is the shortest path algorithm that works on unweighted graphs, that is, graphs in which each edge can be considered to have unit weight.

In a Single Source Shortest Paths Problem, we are given a Graph G = (V, E), we want to find the shortest path from a given source vertex s ∈ V to every vertex v ∈ V.

There are some variants of the shortest path problem.

• Single- destination shortest - paths problem: Find the shortest path to a given destination vertex t from every vertex v. By shift the direction of each edge in the graph, we can shorten this problem to a single - source problem.
• Single - pair shortest - path problem: Find the shortest path from u to v for given vertices u and v. If we determine the single - source problem with source vertex u, we clarify this problem also. Furthermore, no algorithms for this problem are known that run asymptotically faster than the best single - source algorithms in the worst case.
• All - pairs shortest - paths problem: Find the shortest path from u to v for every pair of vertices u and v. Running a single - source algorithm once from each vertex can clarify this problem; but it can generally be solved faster, and its structure is of interest in the own right.

Prim’s algorithm for finding MST

Prim’s algorithm for finding MST (Minimum Spanning Tree)

Prim's algorithm to find minimum cost spanning tree uses the greedy approach. Prim's algorithm, in contrast with Kruskal's algorithm, treats the nodes as a single tree and keeps on adding new nodes to the spanning tree from the given graph.

Example:

Step 1 - Remove all loops and parallel edges. 

In case of parallel edges, keep the one which has the least cost associated and remove all others.

Step 2 - Choose any arbitrary node as root node

In this case, we choose S node as the root node of Prim's spanning tree. This node is arbitrarily chosen, so any node can be the root node. 

Step 3 - Check outgoing edges and select the one with less cost

After choosing the root node S, we see that S,A and S,C are two edges with weight 7 and 8, respectively. We choose the edge S,A as it is lesser than the other.

We check for all edges going out from (S,A). We select the one which has the lowest cost and include it in the tree.

This process is repeated until all the nodes in the graph are covered.

Example 2:

Kruskal’s algorithm for finding MST

Kruskal’s algorithm for finding MST(Minimum Spanning Tree)

Kruskal's algorithm to find the minimum cost spanning tree uses the greedy approach.

To understand Kruskal's algorithm let us consider the following example –

Step 1 - Remove all loops and Parallel Edges

In case of parallel edges, keep the one which has the least cost associated and remove all others.

Step 2 - Arrange all edges in their increasing order of weight

Step 3 - Add the edge which has the least weightage

Now we start adding edges to the graph beginning from the one which has the least weight. Throughout, we shall keep checking that the spanning properties remain intact. In case, by adding one edge, the spanning tree property does not hold (forms a cycle) then we shall not include the edge in the graph.

The least cost is 2 and edges involved are B,D and D,T. We add them.

Next cost is 3, and associated edges are A,C and C,D. We add them again –

Next cost in the table is 4, and we observe that adding it will create a circuit in the graph. We ignore it.

We observe that edges with cost 5 and 6 also create circuits. We ignore them and move on.

Now we are left with only one node to be added. Between the two least cost edges available 7 and 8, we shall add the edge with cost 7.

By adding edge S,A we have included all the nodes of the graph and we now have minimum cost spanning tree.

Example 2: