Pseudokod na c# (algorytm dijkstry)

0

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

0

Ale czego nie umiesz? Jeśli masz chociaż podstawową wiedzę na temat składni C# to powinieneś sobie spokojnie poradzić z przepisaniem większości tego kodu (chyba że chodzi o konkretne niejasne miejsce).
Nie daj się zmylić tym dziwnym symbolom, np. := to w C# =, to != etc.

0

Nie no, aż taki zacofany to nie jestem :)
Bardziej chodzi mi o coś w stylu:

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]

co mam rozumieć przez pusty rekord jeżeli rekord to obiekt typu:

 
class ListaRekordow
    {
        public int arc { get; set; }                    // łuk arc wychodzacy z wierzchołka
        public double wartosc { get; set; }        // waga ścieżki zawierającej łuk arc
        public double deltaWartosc { get; set; } // strata w wadze ścieżki wynikająca z włączenia do scieżki łuku arc

        public ListaRekordow(int arc, double wartosc, double deltaWartosc)
        {
            this.arc = arc;
            this.wartosc = wartosc;
            this.deltaWartosc = deltaWartosc;
        }
    }

mam dodać jeszcze jeden konstruktor?

  public ListaRekordow(){}

Czy najbardziej odpowiednią pętlą dla:
4: for all vi ∈ V do
5: T[vi] := ∅; // pusta lista rekordów dla wierzchołka vi
6: end for

będzie foreach?

Podsumowując - proszę aby ktoś wytłumaczył mi to na "chłopski rozum" :)

0

for all vi ∈ V do

foreach (var vi in V)

a co do , to możesz użyć w to miejsce null.

1 użytkowników online, w tym zalogowanych: 0, gości: 1