2
PI (Fach) / Graphen: Algorithmen (Lektion)
Graphen: Algorithmen
Diese Lektion wurde von blace erstellt.
Diese Lektion ist leider nicht zum lernen freigegeben.
- Was besagt das Optimalitätsprinzip im Kontext von kürzesten Wegen in Distanzgraphen? Dass optimalitätsprinzip besagt, dass wenn p(v0,vk) = v0,....,vk) der kürzeste Weg ist, so ist p=(vi,vj) mit 0>=i<j<=k ebenfalls der kürzeste Weg
- Welche Invarianten gelten im Zusammenhang mit kürzesten Wegen in Distanzgraphen? Invarianten– für alle sp(s,v) und alle Kanten (v,v' ) gilt:c(sp(s,v)) + c((v,v')) ≥ c(sp(s,v'))– für mindestens einen sp(s,v) undmindestens eine Kante (v,v’) gilt:c(sp(s,v))+c(v,v’)=c(sp(s,v’)