Algorithm concepts

#!/usr/local/bin/python3 class Graph: def __init__(self): self.num_nodes = 0 self.num_edges = 0 self.nodes = [] # contains all the nodes self.edges = {} # contains adjacency list representation of edges self.input_mode = input("enter the input mode(manual-m/file-f): ") if self.input_mode.lower() == 'f': self.input_file = open(input("enter the graph input file path: ")) self.file_input() else: self.manual_input() def file_input(self): self.num_nodes = int(self.input_file.readline().strip()) for idx in range(self.num_nodes): node_label = self.input_file.readline().strip() self.nodes.append(node_label) self.edges[node_label] = [] # adding an empty list for each newly added node self.num_edges = int(self.input_file.readline().strip()) for idx in range(self.num_edges): edge_src = self.input_file.readline().strip() edge_dest = self.input_file.readline().strip() edge_weight = self.input_file.readline().strip() self.edges[edge_src].append((edge_dest, int(edge_weight))) self.edges[edge_dest].append((edge_src, int(edge_weight))) def manual_input(self): self.num_nodes = int(input()) for idx in range(self.num_nodes): node_label = input() self.nodes.append(node_label) self.edges[node_label] = [] # adding an empty list for each newly added node self.num_edges = int(input()) for idx in range(self.num_edges): edge_src = input() edge_dest = input() edge_weight = input() self.edges[edge_src].append((edge_dest, int(edge_weight))) self.edges[edge_dest].append((edge_src, int(edge_weight))) # display adjacency list representation of graph def display_graph(self): print('\nAdjacency List Representation') print('*' + 45 * '=' + '*') print('| {0: <1} | {1: <30} |'.format('Source Node', 'Edges (destination, weight)')) print('*' + 45 * '=' + '*') for node, edges in self.edges.items(): print('| {0: <11} | {1: <30} |'.format(node, ', '.join(['(' + edge[0] + ',' + str(edge[1]) + ')' for edge in edges]))) print('-' * 47) def dijkstra(self): max_int = 10 ** 9 src_node = None if self.input_mode == 'm': src_node = input("enter the source node label to calculate shortest path: ") else: src_node = self.input_file.readline() if src_node not in self.nodes: print('Invalid source node {} provided. Please provide a valid source.'.format(src_node)) self.dijkstra() dist = {} # all initial nodes are undiscovered and thus assumed at very large (theoretically infinite distance) shortest_path = {} included = {} # all the undiscovered nodes will be set to false for node in self.nodes: dist[node] = max_int included[node] = False shortest_path[node] = [] dist[src_node] = 0 # distance of source node from itself will be ZERO for _ in range(self.num_nodes): min_dist = max_int min_dist_node = None for node in self.nodes: if not included[node] and min_dist > dist[node]: min_dist = dist[node] min_dist_node = node included[min_dist_node] = True for dest_weight in self.edges[min_dist_node]: node, weight = dest_weight[0], dest_weight[1] if dist[min_dist_node] + weight < dist[node]: dist[node] = dist[min_dist_node] + weight shortest_path[node] = shortest_path[min_dist_node] + [node] print('\nDijkstra Shortest Path (Source: {})'.format(src_node)) print('*' + 45 * '=' + '*') print('| {0} | {1: <21} | {2} |'.format('End Node', 'Path', 'Distance')) print('*' + 45 * '=' + '*') for node in dist: print('| {0: <8} | {1: <21} | {2: <8} |'.format(node, ' -> '.join([src_node] + shortest_path[node]), dist[node])) print('-'*47) if __name__ == '__main__': graph = Graph() graph.display_graph() graph.dijkstra()