Home >  Term: DAG korteste baner
DAG korteste baner

Løse én korteste bane problemet i en vektet rettet den asykliske graf 1) gjør en topologisk sortering på hjørnene av kanten så toppunkt uten innkommende er først og hjørner med bare innkommende kantene er vare, 2) tilordner en uendelig avstand hver toppunktet (dist(v) = ∞) og null avstand til kilden, og 3) for hvert toppunkt v i sortert rekkefølge, for hver utgående kant e(v,u), hvis dist(v) + weight(e) < dist(u), angi dist(u) = dist(v) + weight(e) og forgjengeren til du v.

0 0

Creator

  • D.Rambrudt
  •  (V.I.P) 34692 points
  • 100% positive feedback
© 2024 CSOFT International, Ltd.