Повече от един най-кратък път от (s, t) - графика

Въпросът ми е: да предположим, че имаме насочена графика

a-> b (цена 4) a-> c (цена 2)

b-> d (цена 1)

c-> d (цена 3)

Всички ръбове имат дискретни разходи. И има 2 пътя от a до d, които и двете струват 5. Ще има 2 къси пътеки дървета или едно?

Общият въпрос е: Да предположим, че имаме насочена графика, тогава графиката има уникално дърво на шортите?

Това е за присвояване.

Благодарим ви за вашето време.

Отговори:

От Уикипедия (Дърво с най-къс път):

"... дърветата с най-кратък път като цяло не са уникални."

Като цяло може да има няколко най-кратки пътищав графика. По-специално, можете да използвате алгоритъма на Djikstra за изчисляване на най-кратките пътища и този алгоритъм може да върне множество пътища от всеки възел A до всеки друг възел B.

Те не са уникални, тъй като това зависи от върха на източника (за exp: като в dijsktra)