INF = 999 def all_sources_shortest_path(graph): num_vertices = len(graph) # Initialize the distance matrix with the graph's adjacency matrix distance = [list(row) for row in graph] # Floyd-Warshall algorithm for k in range(num_vertices): for i in range(num_vertices): for j in range(num_vertices): distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j]) return distance def print_matrix(matrix): for row in matrix: for value in row: if value == INF: print("INF", end="::") else: print(value, end="::") print() def main(): num_vertices = int(input()) # Initialize the graph with INF for unconnected edges graph = [[INF] * num_vertices for _ in range(num_vertices)] # Take input for the edge weights for i in range(num_vertices): for j in range(num_vertices): weight = int(input()) graph[i][j] = weight # Display the directed graph print_matrix(graph) print(" ") print("*** ") # Calculate and display the all sources shortest path result = all_sources_shortest_path(graph) print_matrix(result) if _name_ == "_main_": main()
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter