Dijkstra's Algorithm
How is Dijkstra's algorithm used in graphs? Is the algorithm used for weighted graphs? What sets is the algorithm maintaining?
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
"""
Last update: 340 days ago