최단경로 예제

정답이 아닙니다. 이러한 가장자리의 가중치를 고려하여 더 깊고 두 번째 살펴 보겠습니다. 노드 a에서 노드 b로 경로를 가져가면 5 «비용이 듭니다». 그러나 노드 a에서 노드 c로 의 경로를 노드 b로 가져가면 3개의 비용만 듭니다. 3노드 예제 그래프에서는 출발지와 도착 노드 사이의 두 가지 가능한 경로를 매우 쉽게 확인할 수 있습니다. 그러나 그래프가 훨씬 더 크면 20개의 노드가 있다고 가정해 보겠습니다. 가중치 그래프의 가중치를 고려하여 가장 짧은 경로를 찾는 것이 거의 쉽지 않았을 것입니다. 그리고 더 큰 그래프에 대해 이야기한다면 어떨까요? 실제로 우리가 다루는 대부분의 그래프는 20개 노드보다 훨씬 큽습니다. 이 문제를 해결하기 위해 무차별 대입 접근 방식을 사용하는 것이 얼마나 실현 가능하고 확장 가능하고 효율적일까요? 예를 들어 위의 예제에서 노드 c와 b 사이의 비용, 거리 또는 용량이 8에 가중치가 있는지 확인할 수 있습니다. 야생에서 Dijkstra 의 알고리즘의 가장 일반적인 예는 길 찾기 문제, 방향 을 결정 하거나 GoogleMaps에 경로 찾는 등.

그래서, 우리는 어떻게 그 숫자를 얻었습니까? 처음에는 혼란스러워 보일 수 있지만 부분으로 분해 할 수 있습니다. 어떤 정점을 보고 있든 관계없이 항상 시작부터 현재 정점까지 가장 짧은 거리를 합산하려고 합니다. 간단히 말해서, 우리는 이 예제에서 값 4를 제공하는 테이블의 «가장 짧은 거리» 값을 살펴보겠습니다. 그런 다음 현재 정점에서 검토하는 이웃에 대한 비용을 살펴보겠습니다. 이 경우 b에서 e까지의 비용은 6이므로 4에 추가하겠습니다. Bellman Ford의 알고리즘은 가중치 가중 그래프의 다른 모든 정점까지 소스 정점에서 가장 짧은 경로를 찾는 데 사용됩니다. 가장 짧은 경로에는 주기를 가질 수 없기 때문에 가장 짧은 경로에는 $$n-1$$ 가장자리가 포함되어 있습니다. 다음은 동일한 예제 가중치 그래프가 인접 목록 형식으로 표시됩니다. Dijkstra의 알고리즘은 약간의 초기 설정이 필요합니다. 그러나, 우리가 그것에 도착하기 전에, Dijkstra의 알고리즘을 실행하기위한 단계와 규칙을 빠르게 살펴 보자.

예제 그래프에서는 노드 a를 시작 노드로 시작합니다. 그러나 Dijkstra 를 실행하는 규칙은 가장 짧은 경로를 찾기 위해 통과하고 방문하는 모든 단일 노드에 적용 될 수 있도록 추상화 될 수 있습니다. 이 모든 것이 많은 것 같다면 걱정하지 마십시오 – 그것은 복잡한 것들입니다! 사실, Dijkstra조차도 잘 예시하기 위해 고군분투하는 것은 어려운 문제입니다.