Het Dijkstra-algoritme implementeren in Python: een stapsgewijze tutorial

Waarom Dijkstra’s algoritme leren?

Dijkstra is het standaardalgoritme om het kortste pad te vinden tussen twee punten in een netwerk, met talloze toepassingen. Het is fundamenteel in de informatica en de grafentheorie. Het begrijpen en implementeren ervan opent de deur naar meer geavanceerde graafalgoritmen en -toepassingen.

Het leert ook een waardevolle oplossingsaanpak via een greedy-algoritme, waarbij je bij elke stap de optimale keuze maakt op basis van de huidige informatie.

Deze vaardigheid is overdraagbaar naar andere optimalisatie-algoritmen. Dijkstra’s algoritme is niet in alle scenario’s het efficiëntst, maar kan een goed vertrekpunt zijn bij het oplossen van “kortste-afstand”-problemen.

Voorbeelden zijn onder meer:

• GPS-navigatiesystemen die de snelste route bepalen
• Routeren van datapakketten in computernetwerken
• Bezorgdiensten die routes optimaliseren voor efficiëntie
• Sociale netwerken (voorstellen van connecties)
• Financiën (zoeken naar optimale investeringspaden)
• Projectmanagement (het meest efficiënte workflowtraject vinden)

Zelfs als je in geen van deze dingen geïnteresseerd bent, helpt het implementeren van Dijkstra’s algoritme in Python je om belangrijke concepten te oefenen zoals:

• Python-classes
• Dictionary comprehensions
• List comprehensions
• Prioriteitswachtrijen

Belangrijke concepten rond grafen

Om Dijkstra’s algoritme in Python te implementeren, frissen we eerst een paar essentiële concepten uit de grafentheorie op. Allereerst zijn er de grafen zelf:

Grafen zijn verzamelingen van knopen (vertices) die verbonden zijn door randen. Knopen vertegenwoordigen entiteiten of punten in een netwerk, terwijl randen de verbindingen of relaties daartussen voorstellen.

Grafen kunnen gewogen of ongewogen zijn. In ongewogen grafen hebben alle randen hetzelfde gewicht (vaak 1). In gewogen grafen (inderdaad) heeft elke rand een gewicht, dat vaak kosten, afstand of tijd representeert.

In deze tutorial gebruiken we gewogen grafen, omdat die nodig zijn voor Dijkstra’s algoritme.

Een pad in een graaf is een reeks knopen die door randen verbonden zijn en begint en eindigt bij specifieke knopen. Het kortste pad, waar we in deze tutorial in geïnteresseerd zijn, is het pad met het minimale totale gewicht (afstand, kosten, enz.).

Dijkstra’s algoritme visueel uitgelegd

Voor de rest van de tutorial gebruiken we de laatste graaf die we zagen:

Laten we met Dijkstra’s algoritme het kortste pad proberen te vinden tussen punten B en F, uit minstens zeven mogelijke paden. Eerst doen we dit visueel; later implementeren we het in code.

Eerst initialiseren we het algoritme als volgt:

1. We zetten B als de root (bron)knoop.
2. We zetten de afstanden tussen B en alle andere knopen initieel op oneindig als hun voorlopige afstandswaarden. Voor B zetten we de waarde op 0, omdat dat de afstand tot zichzelf is:

Vervolgens voeren we de volgende stappen iteratief uit:

1. Kies de knoop met de kleinste waarde als de “huidige knoop” en bezoek al zijn buurknopen. Bij het bezoeken van elke buur werken we hun voorlopige waarden bij van oneindig naar hun randgewichten vanaf de bron.
2. Nadat alle buren van de huidige knoop zijn bezocht, markeren we de huidige knoop als “bezocht”. Zodra een knoop als “bezocht” is gemarkeerd, is zijn waarde al het kortste pad vanaf het doel.
3. Het algoritme gaat terug naar stap 1 en kiest de knoop met de kleinste waarde.

In onze graaf heeft B drie buren — A, D en E. Laten we elk van hen bezoeken, beginnend bij de rootknoop, en hun waarden bijwerken (iteratie 1) op basis van hun randgewichten:

In iteratie 2 kiezen we opnieuw de knoop met de kleinste waarde, dit keer — E. Zijn buren zijn C, D en G. B is uitgesloten omdat we die al bezocht hebben. Laten we de waarden van E’s buren bijwerken:

We zetten C’s waarde op 5,6 omdat zijn waarde de cumulatieve som van gewichten van B naar C is. Hetzelfde geldt voor G. Maar let op: D’s waarde blijft 3,5 terwijl die 3,5 + 2,8 = 6,3 had moeten zijn, net als bij de andere knopen.

De regel is dat als de nieuwe cumulatieve som groter is dan de huidige waarde van de knoop, we die niet bijwerken, omdat de knoop al de kortste afstand naar de root weergeeft. In dit geval noteert D’s huidige waarde van 3,5 al de kortste afstand naar B, omdat ze buren zijn.

We gaan zo door totdat alle knopen zijn bezocht. Zodra dat het geval is, hebben we de kortste afstand naar elke knoop vanaf B en kunnen we simpelweg de waarde van B naar F opzoeken.

Samengevat zijn de stappen:

1. Initialiseer de graaf met de bronknoop op waarde 0 en alle andere knopen op oneindig. Begin met de bron als “huidige knoop”.
2. Bezoek alle buurknopen van de huidige knoop en werk hun waarden bij naar de cumulatieve som van gewichten (afstanden) vanaf de bron. Als de huidige waarde van een buur kleiner is dan de cumulatieve som, blijft die hetzelfde. Markeer de “huidige knoop” als voltooid.
3. Markeer de onvoltooide knoop met de minimumwaarde als de “huidige knoop”.
4. Herhaal stappen 2 en 3 totdat alle knopen voltooid zijn.

Stapsgewijze implementatie van het Dijkstra-algoritme in Python

Om je begrip van Dijkstra’s algoritme te verstevigen, leren we het nu stap voor stap in Python te implementeren.

Grafen begrijpen als dictionaries

Eerst hebben we een manier nodig om grafen in Python te representeren — de populairste optie is een dictionary. Als dit onze graaf is:

Dan kunnen we die representeren met de volgende dictionary:

graph = {
   "A": {"B": 3, "C": 3},
   "B": {"A": 3, "D": 3.5, "E": 2.8},
   "C": {"A": 3, "E": 2.8, "F": 3.5},
   "D": {"B": 3.5, "E": 3.1, "G": 10},
   "E": {"B": 2.8, "C": 2.8, "D": 3.1, "G": 7},
   "F": {"G": 2.5, "C": 3.5},
   "G": {"F": 2.5, "E": 7, "D": 10},
}
Mogelijk gemaakt door

Elke key van de dictionary is een knoop en elke value is een dictionary met de buren van de key en de afstanden ernaartoe. Onze graaf heeft zeven knopen, wat betekent dat de dictionary zeven keys moet hebben.

Andere bronnen noemen de bovenstaande dictionary vaak een dictionary-adjacentielijst. We houden ons vanaf nu ook aan die term.

1. Een Graph-class maken

Om onze code modulairder en makkelijker te volgen te maken, implementeren we een eenvoudige Graph-class om grafen te representeren. Onder de motorkap gebruikt die een dictionary-adjacentielijst. Er is ook een methode om eenvoudig verbindingen tussen twee knopen toe te voegen:

class Graph:
   def __init__(self, graph: dict = {}):
       self.graph = graph  # A dictionary for the adjacency list

   def add_edge(self, node1, node2, weight):
       if node1 not in self.graph:  # Check if the node is already added
           self.graph[node1] = {}  # If not, create the node
       self.graph[node1][node2] = weight  # Else, add a connection to its neighbor
Mogelijk gemaakt door

Met deze class kunnen we onze graaf iteratief from scratch opbouwen zoals dit:

G = Graph()

# Add A and its neighbors
G.add_edge("A", "B", 3)
G.add_edge("A", "C", 3)

# Add B and its neighbors
G.add_edge("B", "A", 3)
G.add_edge("B", "D", 3.5)
G.add_edge("B", "E", 2.8)

...
Mogelijk gemaakt door

Of we geven direct een dictionary-adjacentielijst door, wat sneller is:

# Use the dictionary we defined earlier
G = Graph(graph=graph)

G.graph
Mogelijk gemaakt door

{'A': {'B': 3, 'C': 3},
'B': {'A': 3, 'D': 3.5, 'E': 2.8},
'C': {'A': 3, 'E': 2.8, 'F': 3.5},
'D': {'B': 3.5, 'E': 3.1, 'G': 10},
'E': {'B': 2.8, 'C': 2.8, 'D': 3.1, 'G': 7},
'F': {'G': 2.5, 'C': 3.5},
'G': {'F': 2.5, 'E': 7, 'D': 10}}
Mogelijk gemaakt door

2. Een dictionary gebruiken om afstanden vanaf de bron op te slaan

We maken nog een classmethode — dit keer voor het algoritme zelf — shortest_distances:

class Graph:
   def __init__(self, graph: dict = {}):
       self.graph = graph

   # The add_edge method omitted for space

   def shortest_distances(self, source: str):
       # Initialize the values of all nodes with infinity
       distances = {node: float("inf") for node in self.graph}
       distances[source] = 0  # Set the source value to 0

       ...
Mogelijk gemaakt door

Het eerste wat we binnen de methode doen, is een dictionary definiëren die knoop-waardeparen bevat. Deze dictionary wordt bijgewerkt telkens wanneer we een knoop en zijn buren bezoeken. Zoals we in de visuele uitleg noemden, krijgen alle knopen initieel de waarde oneindig, terwijl de bronwaarde 0 is.

Wanneer we klaar zijn met de methode, wordt deze dictionary geretourneerd en bevat die de kortste afstanden naar alle knopen vanaf de bron. We kunnen dan de afstand van B naar F zo vinden:

# Sneak-peek - find the shortest paths from B
distances = G.shortest_distances("B")

to_F = distances["F"]
print(f"The shortest distance from B to F is {to_F}")
Mogelijk gemaakt door

3. Een prioriteitswachtrij gebruiken om over knopen te itereren

Nu hebben we een manier nodig om over de knopen van de graaf te lopen volgens de regels van Dijkstra's algoritme. Als je je herinnert, kiezen we in elke iteratie de knoop met de kleinste waarde en bezoeken we zijn buren.

Je zou kunnen zeggen dat we simpelweg over de dictionary-keys kunnen loopen:

for node in graph.keys():
   ...
Mogelijk gemaakt door

Deze methode werkt niet, omdat we hiermee de knopen niet op basis van hun waarde kunnen sorteren. Eenvoudige arrays zijn dus niet voldoende. Om dit deel van het probleem op te lossen, gebruiken we een prioriteitswachtrij.

Een prioriteitswachtrij lijkt op een gewone lijst (array), maar elk element heeft een extra waarde die de prioriteit weergeeft. Dit is een voorbeeld van een prioriteitswachtrij:

pq = [(3, "A"), (1, "C"), (7, "D")]Mogelijk gemaakt door

Deze wachtrij bevat drie elementen — A, C en D — en elk heeft een prioriteitswaarde die bepaalt hoe er met de wachtrij wordt gewerkt. Python levert een ingebouwde heapq-bibliotheek om met prioriteitswachtrijen te werken:

from heapq import heapify, heappop, heappushMogelijk gemaakt door

De bibliotheek heeft drie functies die voor ons relevant zijn:

• heapify: Zet een lijst met tuples van prioriteit-waardeparen om in een prioriteitswachtrij.
• heappush: Voegt een element toe aan de wachtrij met de bijbehorende prioriteit.
• heappop: Verwijdert en retourneert het element met de hoogste prioriteit (het element met de kleinste waarde).

pq = [(3, "A"), (1, "C"), (7, "D")]

# Convert into a queue object
heapify(pq)

# Return the highest priority value
heappop(pq)
Mogelijk gemaakt door

(1, 'C')Mogelijk gemaakt door

Zoals je ziet konden we, nadat we pq met heapify in een wachtrij hadden omgezet, C extraheren op basis van zijn prioriteit. Laten we een waarde pushen:

heappush(pq, (0, "B"))

heappop(pq)
Mogelijk gemaakt door

(0, 'B')Mogelijk gemaakt door

De wachtrij is correct bijgewerkt op basis van de prioriteit van het nieuwe element, want heappop retourneerde het nieuwe element met prioriteit 0.

Let op: nadat we een item poppen, maakt het geen deel meer uit van de wachtrij.

Terug naar ons algoritme: nadat we distances initialiseren, maken we een nieuwe prioriteitswachtrij aan die aanvankelijk alleen de bronknoop bevat:

class Graph:
   def __init__(self, graph: dict = {}):
       self.graph = graph

   def shortest_distances(self, source: str):
       # Initialize the values of all nodes with infinity
       distances = {node: float("inf") for node in self.graph}
       distances[source] = 0  # Set the source value to 0

       # Initialize a priority queue
       pq = [(0, source)]
       heapify(pq)

       # Create a set to hold visited nodes
       visited = set()
Mogelijk gemaakt door

De prioriteit van elk element in pq is zijn huidige waarde. We initialiseren ook een lege set om bezochte knopen bij te houden.

4. Het Dijkstra-algoritme als een while-lus

Nu beginnen we te itereren over alle onbezochte knopen met een while-lus:

class Graph:
   def __init__(self, graph: dict = {}):
       self.graph = graph

   def shortest_distances(self, source: str):
       # Initialize the values of all nodes with infinity
       distances = {node: float("inf") for node in self.graph}
       distances[source] = 0  # Set the source value to 0

       # Initialize a priority queue
       pq = [(0, source)]
       heapify(pq)

       # Create a set to hold visited nodes
       visited = set()

       while pq:  # While the priority queue isn't empty
           current_distance, current_node = heappop(
               pq
           )  # Get the node with the min distance

           if current_node in visited:
               continue  # Skip already visited nodes
           visited.add(current_node)  # Else, add the node to visited set
Mogelijk gemaakt door

Zolang de prioriteitswachtrij niet leeg is, blijven we de knoop met de hoogste prioriteit (met de minimale waarde) poppen en zijn waarde en naam toewijzen aan current_distance en current_node. Als current_node in visited zit, slaan we die over. Anders markeren we hem als bezocht en gaan we verder met het bezoeken van zijn buren:

while pq:  # While the priority queue isn't empty
   current_distance, current_node = heappop(pq)

   if current_node in visited:
       continue 
   visited.add(current_node)

   for neighbor, weight in self.graph[current_node].items():
       # Calculate the distance from current_node to the neighbor
       tentative_distance = current_distance + weight
       if tentative_distance < distances[neighbor]:
           distances[neighbor] = tentative_distance
           heappush(pq, (tentative_distance, neighbor))

return distances
Mogelijk gemaakt door

Voor elke buur berekenen we de voorlopige afstand vanaf de huidige knoop door het huidige waarde van de buur op te tellen bij het verbindende randgewicht. Vervolgens controleren we of deze afstand kleiner is dan de afstand van de buur in distances. Zo ja, dan werken we de distances-dictionary bij en voegen we de buur met zijn voorlopige afstand toe aan de prioriteitswachtrij.

Dat is het! We hebben Dijkstra's algoritme geïmplementeerd. Laten we het testen:

G = Graph(graph)

distances = G.shortest_distances("B")
print(distances, "\n")

to_F = distances["F"]
print(f"The shortest distance from B to F is {to_F}")
Mogelijk gemaakt door

{'A': 3, 'B': 0, 'C': 5.6, 'D': 3.5, 'E': 2.8, 'F': 9.1, 'G': 9.8}

The shortest distance from B to F is 9.1
Mogelijk gemaakt door

Dus, de afstand van B naar F is 9,1. Maar wacht: welk pad is dat?

5. Het kortste pad construeren

We hebben nu alleen de kortste afstanden en niet de paden, waardoor onze graaf er zo uitziet:

Om het kortste pad te construeren op basis van de berekende kortste afstand, kunnen we vanaf het doel terugredeneren. Voor elke rand die aan F grenst, trekken we het gewicht ervan af:

1. 9,1–3,5 = 5,6
2. 9,1–2,5 = 6,5

Vervolgens kijken we of een van de resultaten overeenkomt met de waarde van F’s buren. Alleen 5,6 komt overeen met C’s waarde, wat betekent dat C deel uitmaakt van het kortste pad.

We herhalen dit proces opnieuw voor C’s buren A en E:

1. 5,6–3 = 2,6
2. 5,6–2,8 = 2,8

Omdat 2,8 overeenkomt met E’s waarde, maakt die deel uit van het kortste pad. E is ook een buur van B, wat het kortste pad tussen B en F maakt — BECF.

Laten we de implementatie van dit proces aan onze class toevoegen. De code zelf is een beetje anders dan de bovenstaande uitleg, omdat die de kortste paden tussen B en alle andere knopen vindt, niet alleen F.

Ook doet die dit in omgekeerde volgorde, maar het idee is hetzelfde.

Voeg de volgende regels code toe aan het einde van de methode shortest_distances en verwijder de oude return-instructie:

predecessors = {node: None for node in self.graph}

for node, distance in distances.items():
   for neighbor, weight in self.graph[node].items():
       if distances[neighbor] == distance + weight:
           predecessors[neighbor] = node

return distances, predecessors
Mogelijk gemaakt door

Wanneer de code draait, bevat de dictionary predecessors de directe ouder van elke knoop die betrokken is bij het kortste pad naar de bron. Laten we het proberen:

G = Graph(graph)

distances, predecessors = G.shortest_distances("B")

print(predecessors)
Mogelijk gemaakt door

{'A': 'B', 'B': None, 'C': 'E', 'D': 'B', 'E': 'B', 'F': 'C', 'G': 'E'}Mogelijk gemaakt door

Eerst zoeken we het kortste pad handmatig met behulp van de dictionary predecessors door terug te lopen vanaf F:

# Check the predecessor of F
predecessors["F"]
Mogelijk gemaakt door

'C'  # It is CMogelijk gemaakt door

# Check the predecessor of C
predecessors["C"]
Mogelijk gemaakt door

'E'  # It is EMogelijk gemaakt door

# Check the predecessor of E
predecessors["E"]
Mogelijk gemaakt door

'B'  # It is BMogelijk gemaakt door

Kijk aan! De dictionary laat correct zien dat het kortste pad tussen B en F BECF is.

Maar we hebben de methode half-handmatig gebruikt. We willen een methode die automatisch het kortste pad retourneert dat is opgebouwd uit de dictionary predecessors, van elke bron naar elk doel. We definiëren deze methode als shortest_path (voeg hem toe aan het einde van de class):

def shortest_path(self, source: str, target: str):
   # Generate the predecessors dict
   _, predecessors = self.shortest_distances(source)

   path = []
   current_node = target

   # Backtrack from the target node using predecessors
   while current_node:
       path.append(current_node)
       current_node = predecessors[current_node]

   # Reverse the path and return it
   path.reverse()

   return path
Mogelijk gemaakt door

Door de functie shortest_distances te gebruiken, genereren we de dictionary predecessors. Daarna starten we een while-lus die bij elke iteratie één knoop teruggaat vanaf de huidige knoop totdat de bronknoop is bereikt. Vervolgens retourneren we de omgekeerde lijst, die het pad van de bron naar het doel bevat.

Laten we het testen:

G = Graph(graph)

G.shortest_path("B", "F")
Mogelijk gemaakt door

['B', 'E', 'C', 'F']Mogelijk gemaakt door

Werkt! Laten we nog eentje proberen:

G.shortest_path("A", "G")Mogelijk gemaakt door

['A', 'C', 'F', 'G']Mogelijk gemaakt door

Helemaal goed.

Conclusie

In deze tutorial leerden we een van de meest fundamentele algoritmen in de grafentheorie — Dijkstra’s. Het is vaak het standaardalgoritme om het kortste pad te vinden tussen twee punten in graafachtige structuren. Door zijn eenvoud heeft het toepassingen in veel sectoren, zoals:

• Logistiek en transport
• Netwerken en telecommunicatie
• Productie en robotica
• Financiën en investeren
• Stedelijke planning

Hopelijk heeft het implementeren van Dijkstra’s algoritme in Python je interesse gewekt voor de wondere wereld van graafalgoritmen. Wil je meer leren, dan raad ik de volgende bronnen van harte aan:

• Cursus Introduction to Network Analysis in Python
• Cursus Data Structures And Algorithms in Python