Pseudo Code

Lektion 4 von 9 im Kurs Dijkstra-Algorithmus - Graph-Algorithmen von Coddy.

dijkstra(n, edges, source):
   dist = [INF, INF, ...]; dist[source] = 0
   visited = all false
   repeat n times:
      u = unvisited vertex with smallest dist (none reachable -> stop)
      visited[u] = true
      for each edge (a -> b, weight w):
         if a == u and dist[u] + w < dist[b]:
            dist[b] = dist[u] + w
   replace every remaining INF with -1
   return dist

INF ist einfach eine Zahl, die größer als jede reale Distanz ist (zum Beispiel 1000000000).
In jeder Runde den nicht besuchten Knoten mit der kleinsten Distanz auszuwählen, ist der Greedy-Kern von Dijkstra. Das Scannen der flachen Kantenliste zum Relaxieren hält den Code einfach und funktioniert in jeder Sprache.

Probier es selbst

Diese Lektion enthält keine Programmieraufgabe.

Teste dich selbst

Diese Lektion enthält ein kurzes Quiz. Starte die Lektion, um es zu beantworten und deinen Fortschritt zu speichern.

Alle Lektionen in Dijkstra-Algorithmus - Graph-Algorithmen

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2