유향 그래프의 최단 경로 찾기

Question

(u, v) ∈ E의 가장자리 가중치가 w(u, v) 인 유향 그래프 G = [V ; E]이 있습니다.

는 {d[v], π[v]}; v ∈ V의 값을 가정하고이이 문을 수행하는 허위 사실 또는 만약 내가 확인할 수있는 방법, 최단 경로의 길이와

그 v ∈ V 센터로 이전 노드 것을

주장 최단 경로 문제를 처음부터 풀지는 않습니까?

각 정점 v에 대한 그이 그래프의 노드 s, 그리고 :이

Answer 1

문제는 조금 불분명하지만, 명확히하기 위해 .. 내 머리에없는 많은 아이디어와 만난 문제

1. 는 v != s 들어 pi[v]는 v에서 s으로 최단 경로의 v 인접 노드로 의도된다.
2. d[v]은 v에서 s까지의 최단 거리를 저장하기위한 것입니다.

pi, d으로 지정하면 문제는 뒷 가장자리와 최소 거리가 합법적으로 들어 있음을 확인하는 것입니다. 다음이 확인

쉽게 구현 조건은 :

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 

이 검사에 O (V + E) 시간을 실행.