printf ("= -", dist [i]);
}
getch ();
}
Output: -
DIJKSTAR algoritme
--------------------
Indtast antallet af knuder: 7
Indtast længden matrix af grafen:
00 03 06 99 99 99 99
03 00 02 04 99 99 99
06 02 00 01 04 02 99
99 04 01 00 02 99 04
99 99 04 02 00 02 01
99 99 02 99 02 00 01
99 99 99 04 01 01 00
VERTEX | A B C D E F G
------------------------------------- --------------------------
STATUS | ! ? ? ? ? ? ?
DIST | 0 3 6 99 99 99 99
NÆSTE | * A A A A A A
VERTEX | A B C D E F G
------------------------------------- --------------------------
STATUS | ! ! ? ? ? ? ?
DIST | 0 3 5 7 99 99 99
NÆSTE | * A B B A A A
VERTEX | A B C D E F G
------------------------------------- --------------------------
STATUS | ! ! ! ? ? ? ?
DIST | 0 3 5 6 9 7 99
NÆSTE | * A B C C C A
VERTEX | A B C D E F G
------------------------------------- --------------------------
STATUS | ! ! ! ! ? ? ?
DIST | 0 3 5 6 8 7 10
NÆSTE | * A B C D C D
VERTEX | A B C D E F G
------------------------------------- --------------------------
STATUS | ! ! ! ! ? ! ?
DIST | 0 3 5 6 8 7 8
NÆSTE | * A B C D C F
VERTEX | A B C D E F G
------------------------------------- --------------------------
STATUS | ! ! ! ! ! ! ?
DIST | 0 3 5 6 8 7 8
NÆSTE | * A B C D C F
VERTEX | A B C D E F G
------------------------------------- --------------------------
STATUS | ! ! ! ! ! ! !
DIST | 0 3 5 6 8 7 8
NÆSTE | * A B C D C F
Kanterne indgår i spaning træet er: -
AB BC CD DE CF FG
** VÆGT AF MINIMAL SPANING træ er = 3 + 2 + 1 + 2 + 2 + 1
= 11
korteste afstand fra
G -> A = G-> F-> C-> B -> A = 8
F -> A = F-> C-> B-> A = 7
E -> A = E-> D-> C-> B-> A = 8
D -> A = D-> C-> B-> A = 6
C -> A = C-> B-> A = 5
B -> A = B-> A = 3
Diskussion: -.
1. Køretid kompleksiteten af algoritmen er O (elogv)
2. En anden metode til at finde den mindste udspændende træ er Kruskal algoritme.
3. I denne algoritme 99 anvendes, hvis den korteste vej mellem et par