Dijkstra's Shortest Path

Giriş
Dijkstra'ya ait güzel bir cümle şöyle

Besides a mathematical inclination, an exceptionally good mastery of one’s native tongue is the most vital asset of a competent programmer. Edsger W.Dijkstra in “How do we tell truths that might hurt?”, EWD498, 1975

Arada engeller varsa A* Algoritması kullanılır. Eğer düğümler arasındaki cost eksi değer ise Floyd Warshall Algoritması kullanılabilir.

Eksi Değere Sahip Bağlantılar Olmamalı
Şu graph için algoritma çalışmaz.

Algoritma Çıktısı

Toplam Mesafe, İzlenilecek Yol, Next Hop gibi bir sürü çıktı olabilir. 

Algoritma belli bir düğüme ulaşınca durabilir veya tüm graph'ı dolaşabilir.

Algoritma - Döngü Kullanan

Çeşitli bitiş koşullar var

1. Düğüm sayısı kadar dolaşan bir örnek burada 

Şöyle yaparız. Ben koda bazı yorumlar ekledim. Benzer bir kodu daha önce bir projede kullandık ancak kodu yazn C kökenli biriydi ve o tarz insanlar için bunlar normal :) 

//Use adjacency matrix representation
void dijkstra(int graph[][], int src) { 
  int dist[] = new int[V]; //the shortest distance from src to i 

  // sptSet[i] will true if vertex i is included in shortest 
  // path tree or shortest distance from src to i is finalized 
  Boolean sptSet[] = new Boolean[V]; 

  // Initialize all distances as INFINITE and stpSet[] as false 
  for (int i = 0; i < V; i++) { 
    dist[i] = Integer.MAX_VALUE; 
    sptSet[i] = false; 
  } 

  // Distance of source vertex from itself is always 0 
  dist[src] = 0; 

  // Find shortest path for all vertices 
  for (int count = 0; count < V - 1; count++) { 
    // Pick the minimum distance vertex from the set of vertices 
    // not yet processed. u is always equal to src in first iteration. 
    //Bu kod yazıda bahsettiğim gereksiz loop'a sebep oluyor
    int u = minDistance(dist, sptSet); 

    // Mark the picked vertex as processed 
    sptSet[u] = true; 

    // Update dist value of the adjacent vertices of the picked vertex.
    for (int v = 0; v < V; v++) 

      // Update dist[v] only if is not in sptSet, there is an 
      // edge from u to v, and total weight of path from src to 
      // v through u is smaller than current value of dist[v] 
      //Bu kod çok saçma yazılmış.
      if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v]) 
        dist[v] = dist[u] + graph[u][v]; 
      } 
  }
}

2. Unvisited düğüm sayısı 0 oluncaya kadar dönen bir örnek burada  Aslında aynı şekilde visited düğüm sayısı graph'a eşit oluncaya kadar da dönülebilir.

Döngü kullanan algoritmalarda bir sürü Integer.MAX_VALUE (veya hangi geçersiz değeri kullanıyorsam) ve benim hesapladığım sayılar arasında en küçük değere sahip yeni düğümü bulmak için loop kullandığı için çok iyi değil.

Priority Queue Kullanılıyorsa

Çeşitli bitiş koşullar var

1. Kuyruk boşalınca algoritma biter.  Bazı kodlarda kuyruğa sürekli ekleme yapılıyor. Çünkü düğümüm visited alanı true ise bu düğüm zaten dikkate alınmaz diye düşünülüyor. Ancak bence bu doğru değil.

Şöyle yaparız. Burada her düğümü gidip Integer.MAX_VALUE gibi bir şeyle ilklendirmeye gerek yok.

public void computeShortestPaths(Vertex sourceVertex){
 
  sourceVertex.setDistance(0);
  PriorityQueue<Vertex> priorityQueue = new PriorityQueue<>();
  priorityQueue.add(sourceVertex);
  sourceVertex.setVisited(true);
 
  while( !priorityQueue.isEmpty() ){
    // Getting the minimum distance vertex from priority queue
    Vertex actualVertex = priorityQueue.poll();
 
    for(Edge edge : actualVertex.getAdjacenciesList()){
      Vertex neighborVertex = edge.getTargetVertex();
      if(!neighborVertex.isVisited()) {
        double newDistance = actualVertex.getDistance() + edge.getWeight();
        if( newDistance < neighborVertex.getDistance() ){
	  //Burada komşu vertex zaten varsa bile çıkar ve tekrar ekle
          priorityQueue.remove(neighborVertex);
          neighborVertex.setDistance(newDistance); //Yeni mesafe değeri
          neighborVertex.setPredecessor(actualVertex); //Belki yolu bulmak için gerekir
          priorityQueue.add(neighborVertex);
        }
      }
    }
    actualVertex.setVisited(true);
  }
}

2. Visited düğüm sayısı tüm graph'a eşit olunca algoritma biter.

Örnek

Elimizde şöyle bir sınıf olsun. Bu kod biraz daha farklı, çünkü seçim kriteri globalScore alanında saklı. Toplam maliyet ise localScore alanında saklı.

class Cell {
  // Normal Cell things..
  int x,y;
  boolean isWall;
  
  int localScore;  // The distance from the start.
  int globalScore; // The distance from the end (heuristic).
  boolean isVisited;
  ...
   
}

Elimizde şöyle bir mesafe hesaplama formülü olsun

// Manhattan distance used for A*.
int distance(Cell cell1, Cell cell2) {
  int deltaX = Math.abs(cell1.x - cell2.x);
  int deltaY = Math.abs(cell1.y - cell2.y);
  return deltaX + deltaY;
}

Liste şöyle olsun

List<Cell> discoveredCells = new ArrayList<>();

Şöyle yaparız. Burada listeye tüm komşular ekleniyor. Hedefe varınca da algoritma duruyor

int findShortestPath() {
  Cell current = station.start();
  current.localScore = 1;
  current.isVisited = false;
  current.globalScore = distance(current, station.end());

  discoveredCells.add(station.start());

  while(!discoveredCells.isEmpty() && current != station.end()) {
    // Get the cell that has the lowest global score - aka lowest potential
    // distance from end. Also remove it from the discovered list.
    discoveredCells = discoveredCells.stream()
      .sorted(Comparator.comparingInt(cell -> cell.globalScore))
      .filter(cell -> !cell.isVisited)
      .collect(Collectors.toList());

    if(discoveredCells.isEmpty()) break;

    current = discoveredCells.remove(0);
    current.isVisited = true;

    for(Cell neighbour : station.getCellNeighbours(current)) {
      // If the neighbour is not already visited and it's not a wall,
      // mark it as discovered.
      if(neighbour.isVisited || neighbour.isWall)
        continue;

      discoveredCells.add(neighbour);

      // If the neighbour's new localScore is lower than
      // the old one => update the cell.
      int possibleNeighbourLocalScore = current.localScore + distance(current, neighbour);
      if(neighbour.localScore > possibleNeighbourLocalScore) {
        neighbour.localScore = possibleNeighbourLocalScore;//Toplam maliyeti güncelle
        neighbour.globalScore = neighbour.localScore + distance(neighbour, station.end());
      }
    }
  }

  if (current == station.end())
    return current.localScore;

  return Integer.MAX_VALUE;
}

Örnek - Priority Queue Çözümü
C# ile şöyle yaparız. Burada listeye sadece maliyeti en küçük olan düğüm ekleniyor. Hedefe varınca da algoritma duruyor.

private void DijkstraSearch()
{
  Start.MinCostToStart = 0;
  var prioQueue = new List<Node>();
  prioQueue.Add(Start);
  do {
    prioQueue = prioQueue.OrderBy(x => x.MinCostToStart).ToList();
    var node = prioQueue.First();
    prioQueue.Remove(node);
    foreach (var cnn in node.Connections.OrderBy(x => x.Cost))
    {
      var childNode = cnn.ConnectedNode;
      if (childNode.Visited)
        continue;
      if (childNode.MinCostToStart == null ||
          node.MinCostToStart + cnn.Cost < childNode.MinCostToStart)
      {
        childNode.MinCostToStart = node.MinCostToStart + cnn.Cost;
        childNode.NearestToStart = node;
          if (!prioQueue.Contains(childNode))
            prioQueue.Add(childNode);
          }
      }
      node.Visited = true;
      if (node == End)
        return;
  } while (prioQueue.Any());
}

Eğer En Kısa Yol Seçilmezse Ne Olur
Elimizde şöyle bir graph olsun.

1'den 4'e giderken en kısa yol seçilmezse 1->3->4 olan yolu seçebiliriz. Bu durumda maliyet 1->2->3->4 üzerinden 3 olacağına 4 olur. Bu da yanlış sonuca sebep olur.

Dynamic Programming
Kod şöyle

int minPathSum(vector<vector<int>>& grid) {
  int m = grid.size();
  int n = grid[0].size(); 
  vector<vector<int> > sum(m, vector<int>(n, grid[0][0]));
  for (int i = 1; i < m; i++)
    sum[i][0] = sum[i - 1][0] + grid[i][0];
  for (int j = 1; j < n; j++)
    sum[0][j] = sum[0][j - 1] + grid[0][j];
  for (int i = 1; i < m; i++)
    for (int j = 1; j < n; j++)
      sum[i][j]  = min(sum[i - 1][j], sum[i][j - 1]) + grid[i][j];
  return sum[m - 1][n - 1];
}

İlk iki döngü m (dikey) ve n (yatay) eksenlerdeki maliyetleri hesaplar. Sonraki iç içe iki döngü ise tüm geri kalan hücreleri dolaşarak maliyeti hesaplar. Elimizdeki grid veri şöyle olsun.

[
[  1,   2, 500]
[100, 500, 500]
[  1,   3,   4]
]

Çıktı olarak sum dizisi şöyledir.

[
[  1,   3,  503]
[101, 503, 1003]
[102, 105,  109]
]

İkinci döngünün açıklaması şöyle

sum[i][j] = min(sum[i - 1][j], // take better path between previous horizontal
                sum[i][j - 1]) // or previous vertical
            + grid[i][j]; // current cost

Bu yöntemim avantajının açıklaması şöyle

Any backtracking/dijkstra/A* algorithm will need to maintain a full matrix as well as a list of open nodes. This Dynamic Programming solution just assumes every node will end up being visited, so it can ditch the open node list and just maintain the costs buffer.

By assuming every node will be visited, it also gets rid of the "which node do I open next" part of the algorithm.