project P1

dijsktra.py

'''
fayoum university
faculty of engineering
Networks and communication course

project 1
implement dijsktra's algorithm


'''


from collections import defaultdict

class Graph():
    def __init__(self):
        """
        self.edges is a dict of all possible next nodes
        e.g. {'X': ['A', 'B', 'C', 'E'], ...}
        self.weights has all the weights between two nodes,
        with the two nodes as a tuple as the key
        e.g. {('X', 'A'): 7, ('X', 'B'): 2, ...}
        """
        self.edges = defaultdict(list)
        self.weights = {}
    
    def add_edge(self, from_node, to_node, weight):
        # Note: assumes edges are bi-directional
        self.edges[from_node].append(to_node)
        self.edges[to_node].append(from_node)
        self.weights[(from_node, to_node)] = weight
        self.weights[(to_node, from_node)] = weight

edges = [
    ('X', 'A', 7),
    ('X', 'B', 2),
    ('X', 'C', 3),
    ('X', 'E', 4),
    ('A', 'B', 3),
    ('A', 'D', 4),
    ('B', 'D', 4),
    ('B', 'H', 5),
    ('C', 'L', 2),
    ('D', 'F', 1),
    ('F', 'H', 3),
    ('G', 'H', 2),
    ('G', 'Y', 2),
    ('I', 'J', 6),
    ('I', 'K', 4),
    ('I', 'L', 4),
    ('J', 'L', 1),
    ('K', 'Y', 5),
]

graph = Graph()

for edge in edges:
    graph.add_edge(*edge)

def dijsktra(graph, initial, end):
    # TODO implement dijsktra's algorithm here
    # solve graph with dijsktra's algorithm to find the shortest path
    # between initial and end nodes
    # params:
    #   graph: Graph object
    #   initial: starting node ex: 'X'
    #   end: ending node ex: 'Y'
    # returns:
    #   path: list of nodes in the path from initial to end nodes
    
    pass