Øvelse: Implementér Dijkstra's Algoritme

I denne øvelse skal I implementere Dijkstra's algoritme i Processing til at finde korteste afstande i en graf, som er repræsenteret med en adjacency matrix. (nabo matrice)

Opgaver:

1. Tegn først grafen på papir ud fra en adjacency matrix, som I selv skal definere i koden.
2. I skal opdele programmet i funktioner, der hver især har et klart ansvar:
   1. Initialisering af søgealgoritmens arrays (afstande og besøgte noder)
   2. Selve Dijkstra-algoritmen
   3. Funktion til at finde den næste node med kortest kendt afstand
   4. Udskrivning af resultaterne i et overskueligt format
   5. Hjælpefunktion til at konvertere nodeindeks til navne (fx 0 → 'A') (optionel men rar at have:-))
3. Jeg har lavet en skabelon, hvor funktionerne er tomme. Jeres opgave er at implementere funktionerne.
4. Test jeres løsning med forskellige grafer og startnoder.

En adjacency matrix er en måde at repræsentere en graf (netværk af noder og kanter) på ved hjælp af et to-dimensionel array (et gitter af tal).

• Hver række og kolonne svarer til en node i grafen.
• Værdien i matrix[c][r] viser vægten (afstand, pris eller omkostning) af kanten mellem node c og node r.
• Hvis der ikke er registreret nogen forbindelse mellem to noder angives dette typisk med et stort tal (fx „∞“ eller Integer.MAX_VALUE).
• Diagonal-elementerne (sammen med sig selv) er normalt 0, fordi afstanden fra en node til sig selv er nul.

   A   B   C   D   E
A [0,  4,  ∞,  2,  ∞]
B [4,  0,  3,  ∞,  ∞]
C [∞,  3,  0,  1,  6]
D [2,  ∞,  1,  0,  3]
E [∞,  ∞,  6,  3,  0]

I matrix’en ovenfor betyder fx tallet 4 i position (A,B), at kanten fra node A til node B har vægten 4, mens „∞“ betyder, at forbindelsen ikke er registreret endnu eller ukendt.

final int INF = Integer.MAX_VALUE;
int[][] matrix;  // Nabo matrice
int nodeCount;   // antallet af nodes
int[] distances; // afstande fra startNode.
boolean[] visited; // liste over besøgte nodes. (true, hvis besøgt)
int[] parent; // liste 
int startNode;
 
void setup() {
  // Initialiser variabler her, fx matrix, nodeCount og startNode
  initSearch();
  runDijkstra(startNode);
  printResults();
}
 
// Initialiserer distances- og besøgte nodes
void initSearch() {
  // - Sæt startnode afstand til 0, og alle andre afstande til ∞.
  // - Marker alle nodes som __ikke besøgte__.
}
 
// Kører Dijkstra's algoritme
void runDijkstra(int startNode) {
  // TODO: Implementér algoritmen 
}
 
// Finder næste node med kortest kendt afstand som _ikke_ er besøgt
int minDistanceNode() {
  // returneres der -1, betyder det, at enten er alle noder besøgt, eller at de resterende noder ikke er forbundne med startnoden
  return -1; // Midlertidig return
}
 
// Printer resultatet med afstande fra startnode
void printResults() {
  // TODO: Implementér udskrivning. 
  // Udskrivning af korteste vej.
}
 
// Hjælpefunktion der giver et bogstavnavn til node ud fra index (fx 0 -> A)
String nodeName(int index) {
  // TODO: Implementér konvertering fra index til navn
  return "";
}

InitSearch

Initialiser distances til INF for alle noder
Sæt distances[start] til 0
Initialiser visited til false for alle noder
Initialiser parent til -1 for alle noder (ingen parent endnu) 

FindMinDistance

Sæt min til INF
Sæt minIndex til -1
For hver node v:
Hvis visited[v] == false og distances[v] <= min:
min = distances[v]
minIndex = v
Returner minIndex 

RunDijkstra

Kald InitSearch(start)
Gentag for nodeCount gange:
u = FindMinDistance()
Hvis u == -1:
Stop løkken
visited[u] = true
For hver node v:
Hvis visited[v] == false og der findes kant mellem u og v:
Hvis distances[u] + graph[u,v] < distances[v]:
distances[v] = distances[u] + graph[u,v]
parent[v] = u  // Opdater parent for v 

PrintResults

Skriv "Korteste afstande fra node " + NodeName(start) + ":"
For hver node v:
Hvis distances[v] == INF:
distStr = "∞"
Ellers:
distStr = distances[v].ToString()
Skriv NodeName(start) + " → " + NodeName(v) + ": " + distStr 

PrintPath

Funktion PrintPath(parent, start, end):
Hvis end == start:
Udskriv NodeName(start)
Stop
Hvis parent[end] == -1:
Udskriv "Ingen sti fra " + NodeName(start) + " til " + NodeName(end)
Stop
PrintPath(parent, start, parent[end])
Udskriv " → " + NodeName(end) 

Når du er færdig, kan du teste koden ved at initialisere din matrix, nodeCount og startNode i setup(), og køre programmet. (test din algoritme på nedestående matrice)

matrix = new int[][] {
  // A   B   C   D   E
  {  0,  6, INF,  1, INF},  // A
  {  6,  0,  5,  2,  2 },   // B
  {INF,  5,  0, INF,  5 },  // C
  {  1,  2, INF,  0,  1 },  // D
  {INF,  2,  5,  1,  0 }    // E
};

Korteste sti fra A til C er:

A -> D -> E -> C

Afstand: 7