HTX Frederikshavn & Hjørring

Dette dokument kan kun læses. Du kan se kildekoden, men ikke gemme ændringer i det. Hvis du mener at dette er en fejl, så skriv det venligst på fejl-oversigt.
===== Opgave: Implementer Dijkstra’s algoritme i C# med en adjacency matrix =====

**Formål:**
Lær at arbejde med grafer repræsenteret som adjacency matrix, og implementer Dijkstra’s algoritme til at finde korteste afstande fra en startnode til alle andre noder i grafen.

**Grafen:**
Brug nedenstående matrix som testgraf (værdien `int.MaxValue` repræsenterer ingen direkte forbindelse):

<code csharp>
const int INF = int.MaxValue;
int[,] graph = {
    // 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>

Matrice fra Analog Dijkstra opgave:
<code csharp>
int INF = int.MaxValue;
            int[,] graph = {
    // A    B    C    D    E    F
    {  0,   4,   2,   INF, INF, INF}, // A
    {  4,   0,   1,   5,   INF, INF}, // B
    {  2,   1,   0,   8,  10,   INF}, // C
    {INF,   5,   8,   0,   2,    6 }, // D
    {INF, INF,  10,   2,   0,    2 }, // E
    {INF, INF, INF,   6,   2,    0 },  // F
}; 
</code>

----

=== Opgavebeskrivelse ===

I skal implementere Dijkstra’s algoritme med følgende trin:

  - **Initialiser data** — opret arrays til afstande (`distances`) og besøgte noder (`visited`).
  - **Find næste node** — find den ubesøgte node med den korteste kendte afstand.
  - **Opdater afstande** — gennemgå alle naboer til den valgte node, og opdater afstande, hvis der findes en   kortere sti via den node.
  - **Gentag** — indtil alle noder er besøgt eller ingen nye noder kan nås.
  - **Udskriv resultatet** — vis korteste afstande fra startnode til alle andre.

----

=== Funktionsskabeloner (uden implementering) ===

<code csharp>
class Dijkstra
{
    const int INF = int.MaxValue;
    int nodeCount;
    int[,] graph;
    int[] distances;
    bool[] visited;


public Dijkstra(int[,] graph)
{
    this.graph = graph;
    nodeCount = graph.GetLength(0);
    distances = new int[nodeCount];
    visited = new bool[nodeCount];
}

public void InitSearch(int start)
{
    // TODO: Initialiser distances og visited arrays
}

public int FindMinDistance()
{
    // TODO: Find ubesøgt node med mindste distance og returner dens indeks
    return -1; // Placeholder
}

public void RunDijkstra(int start)
{
    // TODO: Implementer hovedløkken for Dijkstra’s algoritme
}

public void PrintResults(int start)
{
    // TODO: Udskriv korteste afstande fra startnode til alle andre
}
} </code>

----

=== Hint i pseudokode ===

++++ InitSearch | <code>
Initialiser distances til INF for alle noder
Sæt distances[start] til 0
Initialiser visited til false for alle noder </code>
++++

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

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