#!/usr/bin/python3 # =================================================================== # webpage: www.geeksforgeeks.org/ # shortest-paths-from-all-vertices-to-a-destination/ # title: Shortest paths from all vertices to a destination # ==================================================================== # The concept of representing infinity as an integer violates the # definition of infinity itself. There is no way to represent # infinity as an integer in any programming language. However in # python, as it is a dynamic language, the math or numpy modules # have this capability. The code uses a large integer, and it is # probably good enough. # ---- # import math # INF = math.inf # to check if x is infinite... math.isinf(x) # ---- # import numpy as np # INF = np.inf # to check if x is infinite... np.isinf(x) # ==================================================================== import json from queue import PriorityQueue INF = int(0x3f3f3f3f) # This class represents a directed graph using # adjacency list representation class Graph: def __init__(self, compact_costs) -> None: # ---- No. of vertices self.v = len(compact_costs) # ---- In a weighted graph, we need to store vertex # ---- and weight pair for every edge self.adj = [[] for _ in range(self.v)] # ---- adding edges - cost # ---- (source vertex (node), destination vertex (node), # ---- priority (cost)) for r in range(len(compact_costs)): for cols in compact_costs[r][1]: ##print(f'addedge {r} <- {cols[0]} cost={cols[1]})') self.adj[cols[0]].append((r, cols[1])) # ---- calculate the shortest distance from all vertices to # ---- the destination vertex def shortestPath(self, dest: int) -> tuple: # ------------------------------------------------------------ # ---- create a list initialize to 0 # ---- will hold the minimum paths to the destination vertex # ------------------------------------------------------------ paths = [0 for _ in range(self.v)] # ---- create a priority queue to store vertices that # ---- are being preprocessed. This is weird syntax in C++. # ---- Refer below link for details of this syntax # ---- https: # ---- www.geeksforgeeks.org/implement-min-heap-using-stl/ pq = PriorityQueue() # ---- create a vector for distances and initialize all # ---- distances as infinite (INF) dist = [INF for _ in range(self.v)] # ---- insert destination itself in priority queue and # ---- initialize it's distance (cost) to 0 pq.put((0, dest)) dist[dest] = 0 paths[dest] = -1 # minimum path # ---- looping till priority queue becomes empty (or all # ---- distances are not finalized) while not pq.empty(): # ---- the first vertex in pair is the minimum distance # ---- vertex, extract it from priority queue. # ---- vertex label is stored in second of pair (it # ---- has to be done this way to keep the vertices # ---- sorted distance (distance must be first item # ---- in pair) u = pq.get()[1] # ---- 'i' is used to get all adjacent vertices of a vertex for i in self.adj[u]: # ---- Get vertex label and weight of current adjacent # ---- of u. vtx = i[0] weight = i[1] # ---- If there is shorted path to vtx through u. if (dist[vtx] > dist[u] + weight): # ---- Updating distance of vtx dist[vtx] = dist[u] + weight pq.put((dist[vtx], vtx)) paths[vtx] = u # minimum path return (paths,dist) # -------------------------------------------------------------------- # ---- create a x-by-x matrix # ---- initialize to -1 and optionally set the diagonal # ---- # ---- the resultant matrix indexing is: mtx[row][column] # -------------------------------------------------------------------- def create_init_matrix(size,diag=None): mtx = [ [-1 for i in range(size)] for j in range(size)] if diag is not None: for idx in range(size): mtx[idx][idx] = diag return mtx # -------------------------------------------------------------------- # ---- display information # -------------------------------------------------------------------- def title_str(title,length=70): if not title: t = '-' * length elif len(title) > length: t = title[:length] else: t = title + '-' * (length - len(title)) return t def display_outbound_connections(inbound,max=45): print(title_str('---- outbound connections ',max)) for idx,rcn in enumerate(inbound): print(f'{idx:<2} {str(rcn[1]):33} {rcn[2]}') print(title_str('',max)) def display_matrix(mtx,title=None,max=65): print(title_str(f'---- {title} ',max)) print(' ',end='') for i in range(len(mtx)): print(f'[{i:3}] ',end='') print(' (col is from-node)') for idx,row in enumerate(mtx): print(f'[{idx:3}]',end='') for col in row: print(f' {col:>4},',end='') print(' (row is to-node)') print(title_str(None,max)) # -------------------------------------------------------------------- # ---- output JSON file # -------------------------------------------------------------------- def output_json_file(jdata,outfile): with open(outfile,'w') as ofile: ofile.write(json.dumps(jdata)) # -------------------------------------------------------------------- # ---- input JSON file # -------------------------------------------------------------------- def input_json_file(infile): with open(infile,'r') as ifile: jdata = json.load(ifile) return jdata # -------------------------------------------------------------------- # ---- main # -------------------------------------------------------------------- if __name__ == "__main__": ## ---- outbound connections ------------------------------------- ## ---- source nodes [0] [1] [2] (columns) compact_costs = [ [0, [(1,4), (5,8) ], "home"], [1, [(0,4), (4,6), (2,5)], None], [2, [(3,3), (1,10) ], None], [3, [(2,3), (4,4), (5,5)], "work"], [4, [(3,4), (1,6), (0,2)], None], [5, [(3,5), (0,8) ], "shopping"] ] ## ---- original test data from web ------------------------------ ## ---- outbound connections ------------------------------------- ##compact_costs = [ [0, [(2,1), (4,5) ], "home"], ## [1, [(4,1) ], None], ## [2, [(0,10), (3,5) ], "work"], ## [3, [(1,1) ], None], ## [4, [(0,5), (2,100), (3,5)], "shopping"] ] siz = len(compact_costs) print() display_outbound_connections(compact_costs) print() print(f'number of vertices: {siz}') # ---- create a graph g = Graph(compact_costs) # ---- calculate minimum paths and accumulated costs to # ---- all vertices (destination nodes) minimum_paths = [] # paths matrix accumulated_costs = [] # acc costs matrix for row in range(siz): ##print(f'calculate row = {row}') min_path,acc_cost = g.shortestPath(row) minimum_paths.append(min_path) accumulated_costs.append(acc_cost) print() display_matrix(accumulated_costs,'accumulated costs') print() display_matrix(minimum_paths,'minimum paths') print() # ---- now might be a good time to write the minimum paths matrix # ---- to a JSON file so it can be read and used by other programs