HTX Frederikshavn & Hjørring

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

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
};

Matrice fra Analog Dijkstra opgave:

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
}; 

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

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

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
}
} 

InitSearch

Initialiser distances til INF for alle noder
Sæt distances[start] til 0
Initialiser visited til false for alle noder 

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] 

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