Aufgabe:
Betrachten Sie das Problem, einen kürzesten \( s \)-t-Weg zwischen einem Startknoten \( s \in V \) und einem Zielknoten \( t \in V \) in einem gerichteten Graphen \( G=(V, A) \) in Koordinatendarstellung und euklidischen Entfernungen \( c(e)=\|v-w\|, \forall e=(v, w) \in A \) zu finden. Betrachten Sie den modifizierten Algorithmus, der die Kantengewichte
\( c^{\prime}(e):=c(e)+\|w-t\|-\|v-t\| \)
berechnet und dann Dijkstra auf die modifizierten Kantengewichte anwendet.
2.1 Zeigen Sie, dass der Algorithmus einen kürzesten Weg bzgl. \( c^{\prime} \) berechnet.
2.2 Zeigen Sie, dass der Algorithmus auch einen kürzesten Weg bzgl. \( c \) berechnet.
2.3 Was könnte ein Vorteil des modifizierten Algorithmus im Gegensatz zu dem DijkstraAlgorithmus angewendet auf die Kantengewichte \( c \) sein?
Problem/Ansatz:
