Dijkstras 알고리즘 - 부모 노드?

Question

내 교수는 네트워크의 다른 모든 노드에 단일 소스 노드를 구현하기를 원합니다. 그는 부모 노드를 사용하여 최단 경로를 추적한다고했지만 알고리즘의 맥락에서 이것이 무엇을 의미하는지는 알 수 없습니다.

필자는 출력 거리가 모든 네트워크에서 정확하다는 점에서 다소 제 코드를 올바르게 구현할 수 있습니다.

그러나 대부분의 온라인 리소스는 방문 노드에 대해 이야기하고 주변 노드를 모두 탐색 한 후에 방문으로 표시합니다. 예를 들어 노드 A와 B가 노드 C에 이웃하고 A에 대한 새 거리가 B보다 작 으면 노드 C를 방문 했습니까? 그리고 노드 A에 도착하면 실제로 경로가 이미 기록 된 거리가 실제로 커지게된다는 사실을 알게되면 어떻게 될까요?

Answer 1

Dystra 's algo에서 경로를 얻으려면 각 노드에 대한 최적의 비용을 저장하는 대신 best_cost, from_where 쌍을 저장하십시오. from-where는 best_cost를 생성 한 인접 노드에 대한 핸들입니다.

그런 다음 from_where 포인터를 따라 원점으로 돌아가서 최상의 경로를 얻을 수 있습니다. 나는 "부모"가 2- 튜플/쌍의 from_where 요소에 대한 그의 이름이라고 생각한다.

Answer 2

교수님은 우리가 네트워크의 다른 모든 노드에 단일 소스 노드를 구현하기를 원합니다. 그는 부모 노드를 사용하여 최단 경로를 추적한다고했지만 알고리즘의 맥락에서 이것이 무엇을 의미하는지는 알 수 없습니다.

글쎄, 그것은 각 노드에 대해, 어떤 노드가 가장 짧은 경로에서 왔는지를 저장한다는 것을 의미합니다. 이렇게하면 최단 경로의 거리를 찾을뿐만 아니라 최단 경로 자체를 찾기 위해 알고리즘을 완료 한 후 역순으로 최단 경로를 이동할 수 있습니다.

그러나 대부분의 온라인 리소스 노드를 방문하고 주변의 모든 노드를 탐색 한 번 방문으로 그들을 표시에 대해 이야기.

최소 방문 거리를 가진 방문하지 않은 노드 이후에 방문한 노드를 표시합니다. 음의 거리가없는 한, 거리가 먼 경로를 찾을 수 없습니다. 그래프가 거리가 0보다 작은주기가있는 경우에만 문제가됩니다.