나는 Johnson Algorithm의 유용성을 이해하는 데 어려움이 있습니다. 나는이 분야에 대한 지식을 가진 누군가에게 질문이 정말로 바보 같아야한다고 생각하지만, 나는 그것을 이해할 수 없다. Wikipedia에 따르면 Johnson 알고리즘은 Bellman Ford Algorithm을 사용하여 가장자리의 가중치를 음이 아닌 가중치로 변환 한 다음 Dijkstra 알고리즘을 사용하여 최단 경로를 찾습니다. 그러나 Bellman Ford Algorithm은 최단 경로를 찾는 알고리즘이기도합니다. Bellman Ford Algorithm에서 얻은 최단 경로를 사용하지 않는 이유는 무엇입니까?최단 경로 : Bellman-Ford 대 Johnson
Bellman-Ford 알고리즘은 단일 소스에서 모든 그래프 정점 ("단일 소스 최단 경로")까지의 최단 경로를 찾습니다. Johnson의 알고리즘은 모든 정점에서 다른 모든 정점 ("모든 쌍의 최단 경로")까지의 최단 경로를 찾습니다. 따라서 그래프의 가능한 모든 시작점에서 Bellman-Ford를 실행하는 것과 같습니다.
Bellman Ford 알고리즘은 단일 꼭지점 (소스)에서 다른 모든 꼭지점까지 최단 경로를 찾는 데 사용되지만, Johnson 알고리즘은 모든 쌍의 최단 경로를 찾는 데 사용됩니다. C에서 Johnson 알고리즘을 구현하려면 알립니다.
나는이 파티에 늦었다 고 알고있다. 그러나 나는 단지 나 자신에게 똑같은 것을 요구했기 때문에 질문에 비틀 거렸다.
더 나은 이해를 위해 Johnson의 알고리즘의 첫 번째 단계는 실제로 이 새로운 그래프을 생성한다는 것을 지적하고자합니다. 이 작업은 Bellman-Ford 알고리즘을 사용하여 원래의 그래프 (음의 모서리를 가질 수 있음)를 음의 모서리가없는 다른 (그러나 등가의) 그래프로 변환하여 수행합니다. 이 새로운 그래프는 이제 Dijkstra의 알고리즘과 함께 사용하는 것이 안전합니다. 그런 다음 Dijkstra 's 알고리즘을 사용하여 두 개의 다른 답변에 언급 된 "모든 쌍 최단 경로"를 효율적으로 계산합니다.
여기에 좋은 설명이 있습니다. http://www.geeksforgeeks.org/johnsons-algorithm/