[S.....n]

Uczył się ktoś z „Algorytmy bez tajemnic” Cormena? W sekcji „skierowane grafy acykliczne” jest taki dział, w którym poszukuje się długości najkrótszej ścieżki do danego węzła. Skoro wierzchołek źródłowy to s (najkrótsza ścieżka do s wynosi 0), to o co chodzi z wierzchołkiem r? Skoro ścieżka od r do s wynosi 5, to czemu min[s]=0? R to jakiś wierzchołek pomocniczy, punkt startowy?

Nie rozumiem ( ͡° ʖ̯ ͡°)

#pytanie #kiciochpyta #algorytmy #programowanie może #matematyka pomoże

[legolass]

@Snuffkin: To pokazuje najkrótsze ścieżki z wierzchołka s. W tym przykładzie da się dojść z wierzchołka r do s, ale z wierzchołka s do r już, ponieważ graf jest skierowany. Obrazek ma pokazać jakie będą wyniku w przypadku gdy wierzchołek jest nieosiągalny.

[S.....n]

@legolass: Ok, czyli po prostu w tym przypadku stwierdzamy, ze interesują nas tylko ścieżki od s, a nie od r, który jest początkowym wierzchołkiem grafu. Dobrze rozumiem?

[legolass]

@Snuffkin: Tak. W tym przypadku liczone są najkrótsze ścieżki z wierzchołka s do innych wierzchołków.

[snejdan]

@Snuffkin: przecież jest tam napisane.

Cytowany tekst...Nie ma scieżki z s do r, dlatego najkrótsza[r] = nieskończoność

To co jest jest w kółku: nieskończoność, 0, 2, 6, 5, 3 to najkrótsza ścieżka z s do wierzchołków odpowiednio r, s, t, x, y, z. To co na krawędziach to wagi.
Dlatego np przy z jest 3, bo tyle wynosi najkrótsza scieżka z ss do z: idziesz z s do x

[S.....n]

@legolass: dziękuję!
@snejdan: nie wpadłam, ze „nagłówek źródłowy” może oznaczać dowolny nagłówek, od którego liczy się najkrótsze ścieżki, a nie początek grafu jako taki. Już czaję :D i tak, wyglada na to, ze to ten algorytm