Floyd warshall algorithm python

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

The Floyd-Warshall algorithm for the shortest path problem

Xavier-MaYiMing/Floyd-Warshall-Algorithm

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Reference: Floyd R W. Algorithm 97: shortest path[J]. Communications of the ACM, 1962, 5(6): 345.

The Floyd-Warshall Algorithm for the shortest path problem

Variables	Meaning
network	Dictionary, , . >
nn	The number of nodes
dis_mat	List, dis_mat[i][j] denotes the length of the shortest path from node i to node j
path_mat	List, path_mat[i][j] denotes the shortest path from node i to node j

if __name__ == '__main__': test_network = < 0: 1: 62, 2: 44, 3: 67>, 1: 0: 62, 2: 32, 4: 52>, 2: 0: 44, 1: 33, 3: 32, 4: 52>, 3: 0: 67, 2: 32, 4: 54>, 4: 1: 52, 2: 52, 3: 54> > print(main(test_network))

< 'path': [ [[0], [0, 1], [0, 2], [0, 3], [0, 2, 4]], [[1, 0], [1], [1, 2], [1, 2, 3], [1, 4]], [[2, 0], [2, 1], [2], [2, 3], [2, 4]], [[3, 0], [3, 2, 1], [3, 2], [3], [3, 4]], [[4, 2, 0], [4, 1], [4, 2], [4, 3], [4]] ], 'length': [ [0, 62, 44, 67, 88], [62, 0, 32, 65, 52], [44, 33, 0, 32, 52], [67, 64, 32, 0, 54], [104, 52, 52, 54, 0] ] >

About

The Floyd-Warshall algorithm for the shortest path problem

Источник

Floyd-Warshall Algorithm

In this tutorial, you will learn how floyd-warshall algorithm works. Also, you will find working examples of floyd-warshall algorithm in C, C++, Java and Python.

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 (where the sum of the edges in a cycle is negative).

A weighted graph is a graph in which each edge has a numerical value associated with it.

Floyd-Warhshall algorithm is also called as Floyd’s algorithm, Roy-Floyd algorithm, Roy-Warshall algorithm, or WFI algorithm.

This algorithm follows the dynamic programming approach to find the shortest paths.

How Floyd-Warshall Algorithm Works?

Follow the steps below to find the shortest path between all the pairs of vertices.

Create a matrix A 0 of dimension n*n where n is the number of vertices. The row and the column are indexed as i and j respectively. i and j are the vertices of the graph.

Each cell A[i][j] is filled with the distance from the i th vertex to the j th vertex. If there is no path from i th vertex to j th vertex, the cell is left as infinity.
Now, create a matrix A 1 using matrix A 0 . The elements in the first column and the first row are left as they are. The remaining cells are filled in the following way.

Let k be the intermediate vertex in the shortest path from source to destination. In this step, k is the first vertex. A[i][j] is filled with (A[i][k] + A[k][j]) if (A[i][j] > A[i][k] + A[k][j]) .

That is, if the direct distance from the source to the destination is greater than the path through the vertex k , then the cell is filled with A[i][k] + A[k][j] .

In this step, k is vertex 1. We calculate the distance from source vertex to destination vertex through this vertex k.
For example: For A 1 [2, 4] , the direct distance from vertex 2 to 4 is 4 and the sum of the distance from vertex 2 to 4 through vertex (ie. from vertex 2 to 1 and from vertex 1 to 4) is 7. Since 4 < 7 , A 0 [2, 4] is filled with 4. Similarly, A 2 is created using A 1 . The elements in the second column and the second row are left as they are.

In this step, k is the second vertex (i.e. vertex 2). The remaining steps are the same as in step 2.

Similarly, A 3 and A 4 is also created.

A 4 gives the shortest path between each pair of vertices.

Floyd-Warshall Algorithm

n = no of vertices A = matrix of dimension n*n for k = 1 to n for i = 1 to n for j = 1 to n Ak[i, j] = min (Ak-1[i, j], Ak-1[i, k] + Ak-1[k, j]) return A

Python, Java and C/C++ Examples

# Floyd Warshall Algorithm in python # The number of vertices nV = 4 INF = 999 # Algorithm implementation def floyd_warshall(G): distance = list(map(lambda i: list(map(lambda j: j, i)), G)) # Adding vertices individually for k in range(nV): for i in range(nV): for j in range(nV): distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j]) print_solution(distance) # Printing the solution def print_solution(distance): for i in range(nV): for j in range(nV): if(distance[i][j] == INF): print("INF", end=" ") else: print(distance[i][j], end=" ") print(" ") G = [[0, 3, INF, 5], [2, 0, INF, 4], [INF, 1, 0, INF], [INF, INF, 2, 0]] floyd_warshall(G)

// Floyd Warshall Algorithm in Java class FloydWarshall < final static int INF = 9999, nV = 4; // Implementing floyd warshall algorithm void floydWarshall(int graph[][]) < int matrix[][] = new int[nV][nV]; int i, j, k; for (i = 0; i < nV; i++) for (j = 0; j < nV; j++) matrix[i][j] = graph[i][j]; // Adding vertices individually for (k = 0; k < nV; k++) < for (i = 0; i < nV; i++) < for (j = 0; j < nV; j++) < if (matrix[i][k] + matrix[k][j] < matrix[i][j]) matrix[i][j] = matrix[i][k] + matrix[k][j]; >> > printMatrix(matrix); > void printMatrix(int matrix[][]) < for (int i = 0; i < nV; ++i) < for (int j = 0; j < nV; ++j) < if (matrix[i][j] == INF) System.out.print("INF "); else System.out.print(matrix[i][j] + " "); > System.out.println(); > > public static void main(String[] args) < int graph[][] = < < 0, 3, INF, 5 >, < 2, 0, INF, 4 >, < INF, 1, 0, INF >, < INF, INF, 2, 0 > >; FloydWarshall a = new FloydWarshall(); a.floydWarshall(graph); > >

// Floyd-Warshall Algorithm in C #include // defining the number of vertices #define nV 4 #define INF 999 void printMatrix(int matrix[][nV]); // Implementing floyd warshall algorithm void floydWarshall(int graph[][nV]) < int matrix[nV][nV], i, j, k; for (i = 0; i < nV; i++) for (j = 0; j < nV; j++) matrix[i][j] = graph[i][j]; // Adding vertices individually for (k = 0; k < nV; k++) < for (i = 0; i < nV; i++) < for (j = 0; j < nV; j++) < if (matrix[i][k] + matrix[k][j] < matrix[i][j]) matrix[i][j] = matrix[i][k] + matrix[k][j]; >> > printMatrix(matrix); > void printMatrix(int matrix[][nV]) < for (int i = 0; i < nV; i++) < for (int j = 0; j < nV; j++) < if (matrix[i][j] == INF) printf("%4s", "INF"); else printf("%4d", matrix[i][j]); > printf("\n"); > > int main() < int graph[nV][nV] = 0, 3, INF, 5>, 2, 0, INF, 4>, 1, 0, INF>, 2, 0>>; floydWarshall(graph); >

// Floyd-Warshall Algorithm in C++ #include using namespace std; // defining the number of vertices #define nV 4 #define INF 999 void printMatrix(int matrix[][nV]); // Implementing floyd warshall algorithm void floydWarshall(int graph[][nV]) < int matrix[nV][nV], i, j, k; for (i = 0; i < nV; i++) for (j = 0; j < nV; j++) matrix[i][j] = graph[i][j]; // Adding vertices individually for (k = 0; k < nV; k++) < for (i = 0; i < nV; i++) < for (j = 0; j < nV; j++) < if (matrix[i][k] + matrix[k][j] < matrix[i][j]) matrix[i][j] = matrix[i][k] + matrix[k][j]; >> > printMatrix(matrix); > void printMatrix(int matrix[][nV]) < for (int i = 0; i < nV; i++) < for (int j = 0; j < nV; j++) < if (matrix[i][j] == INF) printf("%4s", "INF"); else printf("%4d", matrix[i][j]); > printf("\n"); > > int main() < int graph[nV][nV] = 0, 3, INF, 5>, 2, 0, INF, 4>, 1, 0, INF>, 2, 0>>; floydWarshall(graph); >

Floyd Warshall Algorithm Complexity

Time Complexity

There are three loops. Each loop has constant complexities. So, the time complexity of the Floyd-Warshall algorithm is O(n 3 ) .

Space Complexity

The space complexity of the Floyd-Warshall algorithm is O(n 2 ) .

Floyd Warshall Algorithm Applications

• To find the shortest path is a directed graph
• To find the transitive closure of directed graphs
• To find the Inversion of real matrices
• For testing whether an undirected graph is bipartite

Table of Contents

Free Courses on YouTube

Python Full Course Playlist
105 STL Algorithms in Less Than an Hour
C++ STL Playlist
Learn Node.js
Learn Data Science Full course
Learn Computer Networking Full course

Источник