Witam,
poniższy algorytm to zmodyfikowany algorytm dijkstry, który został rozszerzony o możliwość wyszukiwania k najkrótszych ścieżek.
Problem w tym, że muszę go mieć w C#, a nie wiem jak się to tego zabrać.
W związku z czym, proszę Was o pomoc...
Wejście: G = (V, E, w) – skierowany graf ważony z funkcją wagową w
ve – wierzchołek końcowy
Wyjście: T - listy rekordów opisujących łuki drzewa najkrótszych
ścieżek i łuki stratne
Lista rekordów T zawiera:
arc - łuk wychodzący z wierzchołka vi,
W - waga ścieżki zawierającej łuk arc, (typ double)
Δw - strata w wadze ścieżki wynikającą z włączenia do ścieżki łuku arc. (typ double)
1: procedure ComputeShortestPathTree(G, ve, T)
2: begin
3: Q := ∅; // pusta kolejka zawierająca wierzchołki
4: for all vi ∈ V do
5: T[vi] := ∅; // pusta lista rekordów dla wierzchołka vi
6: end for
7: r.W := 0;
8: r.Δw := 0;
9: r.arc := ∅;
10: T[ve].Insert(r); // wstawienie rekordu r do listy rekordów T[ve]
11: Q.Insert(ve); // wstawienie wierzchołka ve do kolejki Q
12: while Q ≠ ∅ do
13: vi := Q.Pop(); // pobranie pierwszego wierzchołka z kolejki
14: for all (vj, vi) ∈ in[vi] do // dla wszystkich łuków wchodzących do vi
15: r.arc := (vj, vi); // łuk z vj do vi
16: r.W := T[vi][0].W + w(vj, vi); // waga ścieżki z vj do ve
17: T[vj].Insert(r); // wstawienie rekordu r do listy T[vj]
18: Q.Insert(vj); // wstawienie wierzchołka vj do kolejki Q
19: end for
20: end while
21: for all vi ∈ V do
22: if T[vi] ≠ ∅ then // wyznaczono najkrótszą ścieżkę z vi do ve
23: for all r ∈ T[vi] do // wyznaczenie strat dla łuków w liście T[vi]
24: r.Δw := r.W – T[vi][0].W; // wyznaczenie straty dla łuku r.arc
25: end for
26: end if
27: end for
28: return T;
29: end