Algoritmer #1

I forløbet algortimer #1, skal vi lære hvad en algoritme er, hvor vigtigt det er at være meget specifik og stringent ift. udførsel af trin i en algoritme.

Når vi programmerer, handler det ikke kun om at skrive kode, men om at løse problemer på en systematisk måde. For at kunne gøre det effektivt, har vi brug for algoritmer.

En algoritme er en trin-for-trin beskrivelse af, hvordan en opgave kan løses – lidt ligesom en opskrift i et køkken eller en manual til at samle en reol.

Algoritmer ligger bag næsten alt, hvad vi bruger i hverdagen: når vi søger på Google, får anbefalinger på Netflix, eller når vores telefon finder den hurtigste vej hjem. I faget Programmering er forståelsen af algoritmer central, fordi de hjælper os til at skrive smartere, mere effektive og mere pålidelige programmer.

Vi vil beskæftige os med BubbleSort sortering, samt Dijkstra Shortest Path algoritme.

Bubble sort er en simpel sorteringsalgoritme, der gentagne gange gennemgår en liste, sammenligner to tilstødende elementer ad gangen og bytter dem, hvis de er i forkert rækkefølge.

Processen gentages flere gange, indtil listen er sorteret.

Trin:

1. Sammenlign par af nabo-elementer
2. Byt om, hvis det næste element er mindre end det forrige
3. Hop til næste element, og gentag indtil ingen bytninger sker i et genneløb.

1. I første gennemløb sammenligner du n-1 par (her 4 par).
2. I andet gennemløb sammenligner du n-2 par. etc. etc. indtil kun 1 par sammenlignes.

De største elementer „bobler op til toppen” af listen ved hvert gennemløb .

Start: 5, 3, 4, 1, 2

  Sammenlign 5 og 3 → byt → 3, 5, 4, 1, 2
  Sammenlign 5 og 4 → byt → 3, 4, 5, 1, 2
  Sammenlign 5 og 1 → byt → 3, 4, 1, 5, 2
  Sammenlign 5 og 2 → byt → 3, 4, 1, 2, 5  ← største er nu på plads

  Sammenlign 3 og 4 → ingen bytning → 3, 4, 1, 2, 5
  Sammenlign 4 og 1 → byt → 3, 1, 4, 2, 5
  Sammenlign 4 og 2 → byt → 3, 1, 2, 4, 5  ← næststørste er nu på plads

  Sammenlign 3 og 1 → byt → 1, 3, 2, 4, 5
  Sammenlign 3 og 2 → byt → 1, 2, 3, 4, 5

  Sammenlign 1 og 2 → ingen bytning → 1, 2, 3, 4, 5

Sorteret liste: 1, 2, 3, 4, 5

Dijkstra’s algoritme bruges til at finde den korteste vej i et netværk, som fx ruter på et kort eller forbindelser i et netværk. Den lærer dig, hvordan man analyserer og håndterer vægtede grafer, samt hvordan man kan optimere søgningen efter den mest effektive rute. Algoritmen viser, hvordan programmering og matematik arbejder sammen, og hvordan logik kan bruges til at løse praktiske problemer.
At forstå Dijkstra giver dig et solidt fundament for mange avancerede algoritmer inden for netværk, spiludvikling og AI.

• Struktureret problemløsning: Algoritmer lærer os at tænke logisk og dele store problemer op i mindre dele, så de bliver lettere at håndtere.
• Effektivitet: To programmer kan løse den samme opgave, men nogle algoritmer gør det meget hurtigere og med færre ressourcer. Det er vigtigt, når programmer skal køre på alt fra supercomputere til små IoT-enheder.
• Overførbarhed: Når du først forstår en algoritme, kan du bruge den i mange forskellige sammenhænge – på tværs af sprog, platforme og teknologier.
• Forberedelse til fremtiden: Uanset om du vil arbejde med softwareudvikling, dataanalyse, AI eller automation, vil algoritmer være en grundlæggende del af dit værktøjskasse.

At lære algoritmer i Programmering B er altså ikke bare et teoretisk krav, men en praktisk nødvendighed. Det gør dig bedre til at tænke som en programmør og giver dig redskaber, du kan bruge både i studiet og i erhvervslivet.

Dijkstra’s algoritme er en graf-algoritme, der bruges til at finde den korteste vej fra en startnode til alle andre noder i en vægtet graf (hvor kanterne har ikke-negative vægte).

Den er især nyttig inden for:

• Netværksrouting (fx hvordan data sendes hurtigst gennem internettet).
• GPS-navigation (finde den korteste rute).
• Planlægnings- og optimeringsproblemer.

• Video : Dijkstras Shortest Path Algorithm Explained

Hvad er Dijkstra's algoritme?

Dijkstra's algoritme er en metode til at finde den korteste vej mellem to punkter i en graf. Grafen består af noder (punkter) og kanter (forbindelser mellem punkter) med tilknyttede vægte (fx afstand, tid eller pris).

Algoritmen starter fra en valgt startnode og arbejder sig gradvist frem ved at opdatere den korteste kendte afstand til hver node, indtil den finder den korteste vej til målnoden.

Hvordan virker algoritmen?

1. Start ved startnoden med afstand 0 til sig selv, og sæt alle andre noders afstand til uendelig (ukendt).
2. Marker alle noder som ubehandlede.
3. Vælg ubehandlet node med den mindste kendte afstand (i starten er det startnoden).
4. For hver af den valgte nodes naboer, beregn en mulig ny kortere afstand via den valgte node.
5. Hvis den nye afstand er kortere end den tidligere kendte afstand, opdateres afstanden og „forgængeren“ (den node man kommer fra).
6. Marker den valgte node som behandlet.
7. Gentag trin 3-6, indtil alle noder er behandlet, eller målnoden er nået.

• Dijkstra er en greedy algoritme, fordi den altid vælger den korteste (mindste) afstand, der er kendt på det givne tidspunkt.
• Den bygger gradvist et sæt af noder, hvor afstanden til startnoden er kendt som den korteste mulige.
• Den garanterer korrekte løsninger, så længe alle vægte er ikke-negative.

Forestil dig, at vi har en række byer forbundet med veje.

• Hver vej har en „pris“ – som kan være enten rejsetid eller afstand i kilometer.
• Du vil gerne finde den hurtigste eller korteste vej fra din hjemmeby (startnoden) til alle andre byer.

Hvordan gør vi det?

• Først kigger vi på de byer, der ligger tættest på.
• Når vi har fundet den korteste vej til en by, „låser“ vi den og behøver ikke kigge på den igen.
• Så bevæger vi os videre udad, by for by, indtil vi kender de korteste ruter til alle byer.

Det er præcis, hvad Dijkstra’s algoritme gør – den finder systematisk den billigste (korteste) vej.

DIJKSTRA(Graph, start):
For hver node v i Graph:
distance[v] := ∞
previous[v] := UDEFINERET
distance[start] := 0 
 
S := tomt sæt  // noder med fastlagt korteste afstand
Q := alle noder i Graph  // noder vi skal behandle
 
Mens Q ikke er tom:
    u := node i Q med mindste distance[u]
    Fjern u fra Q
 
    For hver nabo v af u:
        alt := distance[u] + vægt(u, v)
        Hvis alt < distance[v]:
            distance[v] := alt
            previous[v] := u
 
    Tilføj u til S
 
Returnér distance[] og previous[]

Hvis vi har en graf med noderne A, B, C og D, og kanterne har vægte, finder Dijkstra:

• Korteste vej fra A til B, C og D.
• Samtidig gemmes ikke kun afstanden, men også hvilken rute man skal gå via (gemt i `previous[]`).

Vi har 6 byer (noder): A, B, C, D, E, F Vejene mellem byerne har følgende „afstand i km“:

• A → B = 7, A → C = 9, A → F = 14
• B → C = 10, B → D = 15
• C → D = 11, C → F = 2
• D → E = 6
• E → F = 9

Der er ingen andre direkte forbindelser.

• 0 betyder, at det er samme by.
• ∞ betyder, at der ikke findes en direkte vej.

int INF = int.MaxValue;
 
int[,] graf = {
    { 0, 7, 9, INF, INF, 14 },
    { 7, 0, 10, 15, INF, INF },
    { 9, 10, 0, 11, INF, 2 },
    { INF, 15, 11, 0, 6, INF },
    { INF, INF, INF, 6, 0, 9 },
    { 14, INF, 2, INF, 9, 0 }
};

Symmetrisk matrix, fordi vi antager at vejene kan køres begge veje.

Ved Dijkstra kan man nu slå afstanden mellem to byer op på graph[i,j].

Antallet af noder er 6 → matrixen er 6×6.

int.MaxValue bruges som uendelig (ingen direkte forbindelse).

• Input: En vægtet graf med ikke-negative vægte, og en startnode.
• Output: De korteste afstande fra startnoden til alle andre noder, samt ruten til hver.
• Algoritme-type: Greedy.

• Tegn grafen, find korteste rute
• Implementering af Dijkstra i C#
• Implementering af Dijkstra i Processing