방향 그래프의 모든 경로에서 최소 무게 가장자리

Question

가장자리에 -ve 또는 + ve 가중치가있는 유향 그래프가있는 경우, 정점에서 정점 d까지의 모든 경로에서 가장 작은 무게 가장자리를 찾는 알고리즘은 무엇입니까? Wikipedia

에서

Answer 1

당신은 단일 소스 최단 경로 문제를 설명하고 있습니다. Dijkstra 's를 사용하여 가장자리가 양수 일 경우 Bellman-Ford 또는 가장자리가 음수 인 경우 Bellman-Ford를 사용하여 해결할 수 있습니다. 이 문제를 해결하기위한

가장 중요한 알고리즘은 다음과 같습니다

1. 다 익스트라의 알고리즘은 단일 소스 최단 경로 문제를 해결합니다.
2. 에지 가중치가 음수이면 Bellman-Ford 알고리즘이 단일 소스 문제를 해결합니다.
3. A * 검색 알고리즘은 발견 속도를 높이기 위해 휴리스틱을 사용하여 단일 쌍 최단 경로를 해결합니다.
4. Floyd-Warshall 알고리즘은 모든 쌍의 최단 경로를 해결합니다.
5. 존슨의 알고리즘은 모든 쌍의 최단 경로를 해결하고 스파 스 그래프의 Floyd-Warshall보다 빠릅니다.
6. 비터 비 알고리즘은 각 노드에서 추가 확률 가중치를 사용하여 가장 짧은 확률 경로 문제를 해결합니다.

Answer 2

나는 모두에게서 s, 예를 들면. 깊이 우선 검색. 그런 다음 d에 도달 할 수있는 모든 노드를 찾습니다 (반대 방향으로 그래프의 d에서 도달 할 수있는 모든 노드). 이제 첫 번째 세트에서 시작하여 두 번째 세트에서 끝나는 가장 작은 무게 가장자리가 필요합니다.