"이전"벡터가없는 Dijkstra 알고리즘

Question

그래프의 모든 노드와 루트/소스 간의 최소 거리를 찾는 데 관심이 있습니다. 모든 링크에는 무게가 있습니다. 내가 the Wikipedia article에 표시된 previous[]을 사용할 필요가 없다고 생각합니다. 각 노드의 부모를 알 필요가 없기 때문입니다. 그 맞습니까? 또한 가중치가 모두 1과 같으면 BFS를 실행할 수 있습니까?

Answer 1

백 포인터가없는 Dijkstra의 알고리즘을 완전히 구현할 수 있습니다. 나는 이것을 알고있다. 왜냐하면 I've done it myself이기 때문이다. :-) 그 결과, 일단 완료되면 최단 경로를 복구 할 수 없지만 완벽하게 잘되어야하는 경로 길이 만 있으면됩니다.

두 번째 질문에 대해서는 그렇습니다. 단위 중량이있는 직접 모드에서 BFS를 사용할 수 있습니다. Dijkstra의 알고리즘은 모든 에지가 동일한 포지티브 비용을 가지면 BFS에서 마주 칠 것 같은 순서로 노드를 방문합니다.