그래프에서 최단 경로를 찾는 알고리즘이 있는지 궁금합니다.그래프에서 경로가 아닌 최단 경로
하나의 꼭지점에서 다른 꼭지점까지의 경로 쌍이있는 그래프가 있습니다. 두 개 또는 그 이상의 경로가 동일한 비용을 갖는다. 이 꼭지점 사이의 모든 최단 경로를 어떻게 표시하고 찾을 수 있습니까? 내가 아는 한 Dijkstra 또는 Bellman-Ford 알고리즘은 최단 경로를 찾을 수 있지만 하나만 선택합니다.
Dijkstra의 알고리즘은 모든 가능한 중간 노드 비용과 싱크에 대한 최단 경로 비용을 제공합니다. 싱크대에서 소스로 깊숙히 첫 번째 검색 (뒤로 이동)을 수행하여 소스에서 싱크까지의 모든 경로를 얻을 수 있습니다. 여기서 가장자리의 비용이 비용의 차이와 동일한 경우에만 (역방향으로) 에지를 탐색합니다. 소스에서 두 노드까지의 최단 경로. 물론 역순으로 경로를 얻지 만 쉽게 뒤집을 수 있습니다.
.
예를 들어 주시겠습니까? 나는 이것을 정확하게 이해했다고 생각하지 않는다. 싱크 정점에서 시작해서 DFS를 시작해야하지만, 가장자리를 통과하는 조건을 이해하지 못합니다. – Berial
싱크 정점에서 시작하여 최단 경로 알고리즘이 소스로부터 거리 20에 있다고 말합니다. . 싱크에 연결되는 세 개의 꼭지점이 있다고 가정하고, a, b, c라고 부르며 싱크 x를 호출합니다. a가 소스로부터 거리 18에 있고 에지 도끼가 가중치 2를 가지고 있다고하자. b는 소스로부터 거리 17이고 bx는 가중치 4이고 c는 소스에서 19이고 cx는 가중치 1이다. 이것은 가장 짧은 것이 있음을 의미한다. 소스에서 싱크까지의 경로. 도끼와 cx로 끝남. 이 절차를 사용하여 ax로 끝나는 모든 경로를 나열한 다음 cx로 끝나는 모든 경로를 나열하십시오. – deinst
좋아, 나는 이걸 쓸 수 있었다고 생각한다. 나는 내 프로그램을 시험해야만하고 모든 것이 괜찮은지 알 수있다. – Berial
Floyd-Warshall을 살펴보십시오. 컴퓨터 과학
상기 플로이드 - 워셜 알고리즘은 (때때로 WFI 알고리즘 또는 로이 플로이드 알고리즘이라고도 )는 가중 된 그래프 에 최단 경로를 찾는 그래프 분석 알고리즘 (함께 양 또는 음의 에지 가중치). 알고리즘을 한 번 실행하면 경로 자체에 대한 세부 정보가 반환되지 않지만 가장 가까운 경로의 길이가 인 모든(합계 가중치)을 찾을 수 있습니다. 알고리즘은 동적 프로그래밍의 예입니다.
이것은 어떻게 도움이 되는가? 문제는 주어진 두 정점 사이의 모든 최단 경로에 관한 것입니다. 한 쌍 밖에 없습니다. –
@ 모론 - 오, 내 실수. Berial이 이러한 알고리즘은 두 개의 특정 노드 사이의 모든 똑같이 짧은 경로가 아니라 모든 두 노드 사이에서 가장 짧은 것으로 나타났다는 인상을 받았습니다. Floyd-Warshall은 두 개의 꼭짓점 사이의 모든 최단 경로가 아닌 그래프에서 최단 경로를 모두 찾습니다. –
가장 짧은 경로를 찾으십시오. 같은 거리의 다른 경로가 있다면 그 경로도 찾으십시오. –