#!/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)
# ====================================================================
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