1+ # floyd_warshall.py
2+ """
3+ The problem is to find the shortest distance between all pairs of vertices in a weighted directed graph that can
4+ have negative edge weights.
5+ """
6+
17from __future__import print_function
28
3- def printDist (dist ,V ):
9+
10+ def _print_dist (dist ,v ):
411print ("\n The shortest path matrix using Floyd Warshall algorithm\n " )
5- for i in range (V ):
6- for j in range (V ):
12+ for i in range (v ):
13+ for j in range (v ):
714if dist [i ][j ]!= float ('inf' ) :
815print (int (dist [i ][j ]),end = "\t " )
916else :
@@ -12,37 +19,84 @@ def printDist(dist, V):
1219
1320
1421
15- def FloydWarshall (graph ,V ):
16- dist = [[float ('inf' )for i in range (V )]for j in range (V )]
22+ def floyd_warshall (graph ,v ):
23+ """
24+ :param graph: 2D array calculated from weight[edge[i, j]]
25+ :type graph: List[List[float]]
26+ :param v: number of vertices
27+ :type v: int
28+ :return: shortest distance between all vertex pairs
29+ distance[u][v] will contain the shortest distance from vertex u to v.
30+
31+ 1. For all edges from v to n, distance[i][j] = weight(edge(i, j)).
32+ 3. The algorithm then performs distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j]) for each
33+ possible pair i, j of vertices.
34+ 4. The above is repeated for each vertex k in the graph.
35+ 5. Whenever distance[i][j] is given a new minimum value, next vertex[i][j] is updated to the next vertex[i][k].
36+ """
37+
38+ dist = [[float ('inf' )for _ in range (v )]for _ in range (v )]
1739
18- for i in range (V ):
19- for j in range (V ):
40+ for i in range (v ):
41+ for j in range (v ):
2042dist [i ][j ]= graph [i ][j ]
2143
22- for k in range (V ):
23- for i in range (V ):
24- for j in range (V ):
44+ # check vertex k against all other vertices (i, j)
45+ for k in range (v ):
46+ # looping through rows of graph array
47+ for i in range (v ):
48+ # looping through columns of graph array
49+ for j in range (v ):
2550if dist [i ][k ]!= float ('inf' )and dist [k ][j ]!= float ('inf' )and dist [i ][k ]+ dist [k ][j ]< dist [i ][j ]:
2651dist [i ][j ]= dist [i ][k ]+ dist [k ][j ]
2752
28- printDist (dist ,V )
53+ _print_dist (dist ,v )
54+ return dist ,v
2955
3056
3157
32- #MAIN
33- V = int (input ("Enter number of vertices: " ))
34- E = int (input ("Enter number of edges: " ))
58+ if __name__ == '__main__' :
59+ v = int (input ("Enter number of vertices: " ))
60+ e = int (input ("Enter number of edges: " ))
61+
62+ graph = [[float ('inf' )for i in range (v )]for j in range (v )]
63+
64+ for i in range (v ):
65+ graph [i ][i ]= 0.0
66+
67+ # src and dst are indices that must be within the array size graph[e][v]
68+ # failure to follow this will result in an error
69+ for i in range (e ):
70+ print ("\n Edge " ,i + 1 )
71+ src = int (input ("Enter source:" ))
72+ dst = int (input ("Enter destination:" ))
73+ weight = float (input ("Enter weight:" ))
74+ graph [src ][dst ]= weight
75+
76+ floyd_warshall (graph ,v )
77+
78+
79+ # Example Input
80+ # Enter number of vertices: 3
81+ # Enter number of edges: 2
3582
36- graph = [[float ('inf' )for i in range (V )]for j in range (V )]
83+ # # generated graph from vertex and edge inputs
84+ # [[inf, inf, inf], [inf, inf, inf], [inf, inf, inf]]
85+ # [[0.0, inf, inf], [inf, 0.0, inf], [inf, inf, 0.0]]
3786
38- for i in range (V ):
39- graph [i ][i ]= 0.0
87+ # specify source, destination and weight for edge #1
88+ # Edge 1
89+ # Enter source:1
90+ # Enter destination:2
91+ # Enter weight:2
4092
41- for i in range (E ):
42- print ("\n Edge " ,i + 1 )
43- src = int (input ("Enter source:" ))
44- dst = int (input ("Enter destination:" ))
45- weight = float (input ("Enter weight:" ))
46- graph [src ][dst ]= weight
93+ # specify source, destination and weight for edge #2
94+ # Edge 2
95+ # Enter source:2
96+ # Enter destination:1
97+ # Enter weight:1
4798
48- FloydWarshall (graph ,V )
99+ # # Expected Output from the vertice, edge and src, dst, weight inputs!!
100+ # 0INFINF
101+ # INF02
102+ # INF10