TU Wien:Diskrete Mathematik für Informatik UE (Gittenberger)/Übungen WS13/Beispiel 24

Find a graph $G=(V,E)$ and two vertices $x,y\in V$ such that Dijkstra’s algorithm does not compute the distance $d(x,y)$ correctly.

Solution

x	2	3	y	Node	Predecessor
0	∞	∞	∞	x	-
	3	1	∞	3	x
	3		2	y	3
	3			2	x

The algorithm finds the path $x-3-y$ with weight 2, while the shortest path from $x$ to $y$ is $x-2-3-y$ with weight 1.

Materialien

Neues Material hinzufügen

E

• Exercise 24.png (details)