oraz jak poruszać się po drzewie
Nie musisz. Dijkstry nie interesuje to drzewo (może poza opcjonalną inicjalizacją która potrzebuje listę wszystkich wierzchołków grafu), interesuje go tylko mapowanie wierzchołek->sąsiedzi, które u Ciebie jest w linked listach.
Użyję jako wzorzec pseudokod z Wikipedii;
1 function Dijkstra(Graph, source):
2 dist[source] ← 0 // Initialization
3
4 create vertex priority queue Q
5
6 for each vertex v in Graph:
7 if v ≠ source
8 dist[v] ← INFINITY // Unknown distance from source to v
9 prev[v] ← UNDEFINED // Predecessor of v
10
11 Q.add_with_priority(v, dist[v])
12
13
14 while Q is not empty: // The main loop
15 u ← Q.extract_min() // Remove and return best vertex
16 for each neighbor v of u: // only v that are still in Q
17 alt ← dist[u] + length(u, v)
18 if alt < dist[v]
19 dist[v] ← alt
20 prev[v] ← u
21 Q.decrease_priority(v, alt)
22
23 return dist, prev
Instead of filling the priority queue with all nodes in the initialization phase, it is also possible to initialize it to contain only source; then, inside the if alt < dist[v] block, the node must be inserted if not already in the queue (instead of performing a decrease_priority operation).[
W Twoim przypadku, wierzchołki to wskaźnik Nazwy*.
Tak naprawdę jedyna część która jest zależna od Twojej reprezentacji grafu to:
16 for each neighbor v of u: // only v that are still in Q
17 alt ← dist[u] + length(u, v)
Ta pętla
for each neighbor v of u:
to po prostu pętla po Twojej linked liście u->Odleglosci.
A to
length(u, v)
to jest pole "kilometry" w Twojej liście.
I na oko to tyle.