Finden Sie den kürzesten Weg für eine gerichtete Grafik

Question

Es gibt eine gerichtete Grafik G = [V ; E] mit Kantengewichten w(u, v) für (u, v) ∈ E.

Angenommen, die Werte für {d[v], π[v]}; v ∈ V und behauptet

, dass diese die Länge des kürzesten Weges und der Vorgängerknoten in

es für v ∈ V sind, wie ich, ob diese Aussage wahr oder falsch ist verifizieren könnte, das tut nicht das gesamte Problem des kürzesten Pfades von Grund auf lösen? Dies ist ein Problem, das ich mit nicht vielen Ideen in meinem Kopf traf ..

Answer 1

Das Problem ein wenig unklar ist, aber zu klären:

Es gibt einen Knoten s in Ihrem Diagramm, und dass für jeden Vertex v:

1. für v != s wird pi[v] soll ein Knoten benachbart zu v sein, die von v zu s auf einem kürzesten Pfad ist.
2. d[v] soll den kürzesten Weg von v bis s speichern.

Das Problem ist, zu überprüfen, da eine pi, d, dass sie berechtigterweise Hinterkanten und minimale Abstände enthalten.

Eine leicht implementiert Bedingung, dass dieser überprüft, ist wie folgt:

For each vertex v 
    Either: 
     v = s and d[v] = 0 
    Or: 
    d[pi[v]] = d[v] - 1 
    d[u] >= d[v] - 1 for each u adjacent to v 
    pi[v] is adjacent to v 

Diese Prüfung läuft in O (V + E) Zeit.