====== Øvelse: Implementér Dijkstra's Algoritme ======

=== Øvelsesbeskrivelse ===

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:**

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

----

=== Hvad er en adjacency matrix? ===

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.

==== Eksempel på adjacency matrix for 5 noder (A til E) ====

<code>
   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]
</code>

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. 


----

===== Skabelon med funktioner =====

<code java>
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 "";
}
</code>

----

===== Hints og eksempler på implementering =====

++++ InitSearch | <code java>
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) </code>
++++

++++ FindMinDistance | <code java>
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 </code>
++++

++++ RunDijkstra | <code java>
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 </code>
++++

++++ PrintResults | <code java>
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 </code>
++++

++++ PrintPath | <code java>
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) </code>
++++

----

==== Test af Algoritme ====

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)

<code java>
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
};
</code>

Korteste sti fra A til C er:
<code>A -> D -> E -> C</code>
Afstand: 7