Dijkstra's Algorithm

The algorithm finds the shortest paths between nodes in a weighted graph.
    Weighted graph vertex
class City:

    def __init__(self, name): = name
        self.routes = {}

    def add_route(self, city, price):
        self.routes[] = price

a = City('Atlanta')
b = City('Boston')
c = City('Chicago')
d = City('Denver')
e = City('El Paso')

a.add_route(b, 100); a.add_route(d, 160)
b.add_route(c, 120); b.add_route(d, 180)
c.add_route(e, 80)
d.add_route(c, 40); d.add_route(e, 140)
e.add_route(b, 100)

Cites = {'Atlanta': a, 'Boston': b, 'Chicago': c, 'Denver': d, 'El Paso': e}

for name, obj in Cites.items(): 
    print(name, obj.routes)

    Atlanta {'Boston': 100, 'Denver': 160}
    Boston {'Chicago': 120, 'Denver': 180}
    Chicago {'El Paso': 80}
    Denver {'Chicago': 40, 'El Paso': 140}
    El Paso {'Boston': 100}
    The CORE algorithm /
    Get the cheapest table, containing all the cheapest prices 
    to get to each city from the STARTING point

def dijkstra_shortest_path(starting_city, destination):

    C = {} # Cheapest prices (table)
    U = [] # Unvisited cities (list)
    V = [] # Visited cities (list)
    P = {} # Cheapest previous stopover city (table) - Look Here

    current = starting_city
    C[] = 0 # The price to itself is 0

    # Loop as long as we have unvisited cities
    while current:        

        if in U:

        # Loop adjacent cities
        for name, price in current.routes.items():
            if name not in V:

            # Price of getting from STARTING to ADJACENT city 
            # using CURRENT city as the second-to-last stop:
            price_through_current_city = C[] + price

            # If the price is the cheapest one we've found so far:
            if name not in C or price_through_current_city < C[name]:

                C[name] = price_through_current_city
                P[name] = # Look Here
        # Break the loop when there are no more unvisited cities
        if len(U) == 0:    
        # Set next unvisited city, the cheapest one
        current_name = min(U, key=lambda city: C[city])
        current = Cites[current_name]
    # We have completed the core algorithm.
    # At this point, the cheapest table contains all the cheapest prices 
    # to get to each city from the STARTING point

    # We build the shortest path using an array:
    shortest_path = []

    # Work backwords from final destination
    current_name =

    # Loop until we reach the starting city:
    while current_name !=

        # Add each current_name to shortest_path

        # Follow each city to its previous stopover city
        current_name = P[current_name]

    # Add the starting city to the path

    # We reverse the path to see it from beginning to end
    return list(reversed(shortest_path))
print(dijkstra_shortest_path(a, b))
print(dijkstra_shortest_path(a, c))
print(dijkstra_shortest_path(a, d))
print(dijkstra_shortest_path(a, e))

    ['Atlanta', 'Boston']
    ['Atlanta', 'Denver', 'Chicago']
    ['Atlanta', 'Denver']
    ['Atlanta', 'Denver', 'Chicago', 'El Paso']
    ['Atlanta', 'Denver', 'Chicago', 'El Paso'] 280
    ['El Paso', 'Boston', 'Denver'] 280

Last update: 55 days ago