minte9

LearnRemember

Dijkstra's Algorithm

The algorithm finds the shortest paths between nodes in a weighted graph.

 
"""
    Weighted graph vertex
"""
class City:

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

    def add_route(self, city, price):
        self.routes[city.name] = 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[current.name] = 0 # The price to itself is 0

    # Loop as long as we have unvisited cities
    while current:        
        V.append(current.name)

        if current.name in U:
            U.remove(current.name)

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

            # Price of getting from STARTING to ADJACENT city 
            # using CURRENT city as the second-to-last stop:
            price_through_current_city = C[current.name] + 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] = current.name # Look Here
                
        # Break the loop when there are no more unvisited cities
        if len(U) == 0:    
            break       
        
        # 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 = destination.name

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

        # Add each current_name to shortest_path
        shortest_path.append(current_name)

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

    # Add the starting city to the path
    shortest_path.append(starting_city.name)

    # 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
"""