Computer Science‎ > ‎

### Algorithms: All to all shortest paths in Graphs - Floyd Warshall Algorithm (with C program source code)

Floyd-Warshall Algorithm

Floyd-Warshall algorithm is a dynamic programming formulation, to solve the all-pairs shortest path problem on directed graphs. It finds shortest path between all nodes in a graph. If finds only the lengths not the path. The algorithm considers the intermediate vertices of a simple path are any vertex present in that path other than the first and last vertex of that path.

### Algorithm

Input Format: Graph is directed and weighted. First two integers must be number of vertices and edges which must be followed by pairs of vertices which has an edge between them.
Analysis: The running time of Floyd-Warshall algorithm is O(V3), determined by the triply nested for loops.

## Floyd Warshall Algorithm - C Program Source code

`#include<stdio.h>#include<assert.h>/* maxVertices represents maximum number of vertices that can be present in the graph. */#define maxVertices   100#define INF 123456789/* Input Format: Graph is directed and weighted. First two integers must be number of vertces and edges    which must be followed by pairs of vertices which has an edge between them.  */int min(int a,int b){        return (a<b)?a:b;}void init(int distance[maxVertices][maxVertices]){        int iter,jter;        for(iter=0;iter<maxVertices;iter++)        {                for(jter=0;jter<maxVertices;jter++)                {                        if(iter==jter)                        {                                distance[iter][jter] = 0;                        }                        else                        {                                distance[iter][jter] = INF;                        }                }        }}void FloydWarshall(int distance[maxVertices][maxVertices],int vertices){        int from,to,via;        for(from=0;from<vertices;from++)        {                for(to=0;to<vertices;to++)                {                        for(via=0;via<vertices;via++)                        {                                distance[from][to] = min(distance[from][to],                                                         distance[from][via]+distance[via][to]);                        }                }        }}int main(){        int graph[maxVertices][maxVertices],size[maxVertices]={0},visited[maxVertices]={0};        int distance[maxVertices][maxVertices];        int vertices,edges,iter,jter;        /* vertices represent number of vertices and edges represent number of edges in the graph. */        scanf("%d%d",&vertices,&edges);        /*initialize distance between all pairs as infinity*/        init(distance);        int vertex1,vertex2,weight;        /* Here graph[i][j] represent the weight of edge joining i and j */        for(iter=0;iter<edges;iter++)        {                scanf("%d%d%d",&vertex1,&vertex2,&weight);                assert(vertex1>=0 && vertex1<vertices);                assert(vertex2>=0 && vertex2<vertices);                graph[vertex1][vertex2] = weight;                distance[vertex1][vertex2] = weight;        }        FloydWarshall(distance,vertices);        for(iter=0;iter<vertices;iter++)        {                for(jter=0;jter<vertices;jter++)                {                        if(distance[iter][jter]>=INF)                        {                printf("The shortest distance between %d and %d is Infinity\n",iter,jter);                        }                        else                        {                printf("The shortest distance between %d and %d is %d\n",iter,jter,distance[iter][jter]);                        }                }        }        return 0;}`

```Rough Notes about the Algorithm as implemented in the code above:

Input Format: Graph is directed and weighted. First two integers must be number of vertices and
edges which must be followed by pairs of vertices which has an edge between them.

maxVertices represents maximum number of vertices that can be present in the graph.
vertices represent number of vertices and edges represent number of edges in the graph.
graph[i][j] represent the weight of edge joining i and j.
size[maxVertices] is initialed to{0}, represents the size of every vertex i.e. the number of
edges corresponding to the vertex.
visited[maxVertices]={0} represents the vertex that have been visited.
distance[maxVertices][maxVertices] represents the weight of the edge between the two vertices or distance between two vertices.
Initialize the distance between two vertices using init() function.```
```
init() function- It takes the distance matrix as an argument.
For iter=0 to maxVertices – 1
For jter=0 to maxVertices – 1
if(iter == jter)
distance[iter][jter] = 0 //Distance between two same vertices is 0
else
distance[iter][jter] = INF//Distance between different vertices is INF
jter + 1
iter + 1
Where, INF is a very large integer value.
Initialize and input the graph.```
```
Call FloydWarshall function.
• It takes the distance matrix (distance[maxVertices][maxVertices]) and number of
vertices as argument (vertices).
• Initialize integer type from, to, via
For from=0 to vertices-1
For to=0 to vertices-1
For via=0 to vertices-1
distance[from][to] = min(distance[from][to],distance[from][via]+distance[via][to])
via + 1
to + 1
from + 1```
```
This finds the minimum distance from from vertex to to vertex using the min
function. It checks it there are intermediate vertices between the from and to
vertex that form the shortest path between them
• min function returns the minimum of the two integers it takes as argument.
Output the distance between every two vertices.```

Some Important Data Structures and Algorithms, at a glance:

 Arrays : Popular Sorting and Searching Algorithms Bubble Sort Insertion Sort Selection Sort Shell Sort Merge Sort Quick Sort Heap Sort Binary Search Algorithm Basic Data Structures  and Operations on them Stacks Queues Single Linked List Double Linked List Circular Linked List
 Tree Data Structures Binary Search Trees Heaps Height Balanced Trees Graphs and Graph Algorithms Depth First Search Breadth First Search Minimum Spanning Trees: Kruskal Algorithm Minumum Spanning Trees: Prim's Algorithm Dijkstra Algorithm for Shortest Paths Floyd Warshall Algorithm for Shortest Paths Bellman Ford Algorithm Popular Algorithms in Dynamic Programming Dynamic Programming Integer Knapsack problem Matrix Chain Multiplication Longest Common Subsequence Greedy Algorithms Elementary cases : Fractional Knapsack Problem, Task Scheduling Data Compression using Huffman Trees