Algorytm Dijkstry - MarcinG121/INPGProject GitHub Wiki

Algorytm Dijkstry służy do znajdowania najkrotszej ścieżki w grafie. Jest przykładem alogrytmu zachłannego.

Algorytm działa tylko dla grafow w ktorych wagi krawędzi mają wartości dodatnie.

Działanie algorytmu: s - wierzchołek źrodłowy w(i, j) - waga krawędzi między wierzchołkami i, j.

  1. Tworzymy tablicę d z odlegołciami od źrodła dla każdego wierzchołka. Na początku d[s] = 0, d[i] = inf dla każdego innego wierzchołka.
  2. Tworzymy kolejkę priorytetową wierzchołkow w grafie. Priortytetem jest aktualnie wyliczowna odległość od wierzchołka s.
  3. Dopóki kolejka nie jest pusta:
    • usuń z kolejki wierzchołek o najniższym priorytecie (oznaczmy go jako u).
    • dla każdego sąsiada v wierzchołka u:
    • jeżeli d[u] + w(u, v) < d[v] to d[v] := d[u] + w(u, v)
  4. Tablica d zawiera teraz najkrotsze odległości do każdego wierzchołka.
  5. Jeżeli chcemy znać najkrótsze ścieżki musimy dodatkowo stworzyć tablicę p ktora zawiera poprzednika każdego wierzchołka.

Złożoność obliczeniowa Oznaczmy: E - liczba krawędzi, V - liczba wierzchołków

  • O(E logV) - złożoność czasowa W pewnych szczególnych przypadkach złożoność można zmniejszyć

Pseudokod (za https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm):

  create vertex set Q

  for each vertex v in Graph:             // Initialization
      dist[v] ← INFINITY                  // Unknown distance from source to v
      prev[v] ← UNDEFINED                 // Previous node in optimal path from source
      add v to Q                          // All nodes initially in Q (unvisited nodes)

  dist[source] ← 0                        // Distance from source to source
  
  while Q is not empty:
      u ← vertex in Q with min dist[u]    // Node with the least distance
                                          // will be selected first
     remove u from Q 
  
      for each neighbor v of u:           // where v is still in Q.
          alt ← dist[u] + length(u, v)
          if alt < dist[v]:               // A shorter path to v has been found
              dist[v] ← alt 
              prev[v] ← u 

  return dist[], prev[]

Źródła: