는 나는 말했다 문제가 주어졌다 : 최소 스패닝 트리와 최단 경로
(+)와() 정수 무게, 두 정점 사이의 최단 경로를 찾는 알고리즘을 개발과 연결 방향 그래프 주어진다. 는 내가 같은 크루스 칼 년대로 최소 스패닝 트리 알고리즘을 사용하여 다음 MST에서 모든 정점이 하나의 incomming 우위를 가지고 있기 때문에, 다 익스트라의 알고리즘은 부정적인 무게도 작동하는지 보여 아마 다 익스트라의 알고리즘을 사용할 수 있다고 생각.이 소리 공산당은 무엇입니까?
p.s. MST에 방향 그래프의 최단 경로가 있음을 증명하는 데 문제가 있습니다. 모든 정점에 대해 입니다.
먼저 그래프에 음수주기가 없어야합니다.
둘째, 일반적으로 Dikstra는 음수가 적용된 그래프에서는 작동하지 않습니다.
Thirst, Bellman-Ford Algorithm은 directed-negative-weights 그래프에서 최단 경로를 찾는 데 사용될 수 있습니다.
최소 스패닝 트리에 대한 규정 중 하나에는 사이클이 없습니다. Kruskal의 알고리즘은 그것을 증명합니다. 하지만 링크를 주셔서 감사합니다 –
MST를 만들지 않고도 Bellman-ford 알고리즘을 사용할 수 있습니다. 그게 더 빠른 해결책이 될 것 같아요. –
@ReCoNciLiaTiOn 당신은 부정적인 사이클을 가질 수있는 초기 그래프와 나무를 생성하기를 원하기 때문에주기가없는 스패닝 트리를 혼동하고 있습니다. –
MST에 모든 정점에 대한 최단 경로가 포함되어 있음을 증명하는 데 문제가 있습니다.
거짓입니다. 가장자리 가중치 2, 3 및 4가있는 삼각형 그래프를 가져옵니다. MST에는 가중치 2와 3의 가장자리 만 포함되어 있지만 최단 경로에는 가중치 4가 있고 경로에는 MST가 5입니다.
이 경우, 알고리즘에 최소 스패닝 트리를 포함시키는 것은 나쁜 생각처럼 보입니다.
n> = 2에 대한 n 차원 눈금을 고려하십시오. 모든 트리와 마찬가지로 MST는 한 가장자리 만 연결된 잎이 있습니다. n 차원 그리드의 한 점에는 n 개의 다른 방향으로 n 개의 인접 점이 있으므로 MST는 인접 점까지 가능한 모든 최단 경로를 지원하지 않습니다. – mcdowella