# 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 = {}

self.routes[city.name] = price

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

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)

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