Click to Flip Card

### 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: 291 days ago