Dijkstra의 최단 경로 알고리즘이 작동하지 않습니다.

긍정적 인 에지 가중치와 양수 노드 가중치를 가진 그래프가 있습니다. 경로의 길이는 경로를 따라 모든 에지 가중치와 경로를 따라 마주 치는 최대 노드 가중치의 합으로 정의됩니다.Dijkstra의 최단 경로 알고리즘이 작동하지 않습니다.

나는 처음에는 수정 된 Dijkstra가 작동한다고 생각했지만 실패 할 테스트 케이스를 발견했습니다. 이 문제를 해결하려면 어떻게해야합니까? 내가 살펴 봐야 할 표준 알고리즘이 있습니까?

내 수정 된 Dijkstra는 다음과 같습니다. 각 노드에서 지금까지 본 것 중에서 가장 짧은 경로와 최대 노드 가중치를 기록하고이를 사용하여 이웃 노드의 길이를 계산합니다. 자세한 내용은 내 의견을 참조하십시오.

다음은 Dijkstra가 실패한 그래프입니다. http://i.imgur.com/FQhRzXV.jpg 녹색으로 표시된 숫자는 노드 레이블입니다. 파란색은 가중치 (노드 및 에지 가중치)입니다. 노드 1과 노드 7 사이의 최단 경로를 계산하려고합니다 (녹색으로 표시됨). Dijkstra의 문제점은 노드 4가 경로 1-2-3-4 (이전 길이 9 대 후자 길이 13)보다 짧기 때문에 1-8-9-4 경로를 항상 기록한다는 것입니다. 그러나 노드 7에 도달하기 위해서는 1-8-9-4-5-6-7 경로가 1-2-3-4-5-6-7보다 길어야합니다.

출처

2013-09-21 elexhobby

무엇을 시도했으며 왜 실패 했습니까? 수정 된 Dijkstra가 작동 할 것이라고 확신합니다 :-) –

시작 노드를 수정하십시오. 이웃 노드 각각에 대해 한 쌍의 숫자 (해당 이웃 노드에 대한 최단 경로, 지금까지 노드에서 발견 된 최대 노드 가중치)를 저장합니다. 큐에 넣고 최단 경로를 갖는 노드를 선택하십시오. 잇다. 방문한 노드 a에 연결된 새로운 노드 b를 추가하는 동안 노드 a에 대한 경로에서 b <최대 노드 가중치가 발생하면 b의 쌍은 (최대 에지 가중치 ab에 대한 최단 경로이며 최대 노드는 a까지 만난다). 그렇지 않으면 b의 쌍은 (최대 노드까지의 최단 경로 - 노드 b의 + 가중치 + 에지 가중치 ab, 노드 b의 가중치)입니다. – elexhobby

나는 최소 총 무게로 경로를 풀었고 그 경로에서 가장 큰 가중치를 추적한다고 생각합니다. " 나는 문제가 아마 "최소 (총중량과 가장 큰 무게) 경로"를 요구하고 있다고 생각한다. 가장 큰 무게를 추적하기 만하면 해결되지 않습니다. – DanielV

하나 개 순서 큰 다항식 시간을 용서할 수 있다면, 매우 쉽게 알고리즘 :

ModifiedShortestPath(u, v, G) { 
    X = StandardardShorestPath(u, v, G); 
    E = heaviest edge in X 
    F = all edges in G of weight >= E 
    Y = ModifiedShortestPath(u, v, G - F); // recur here on G without the F edges 
    return Min(X, Y); 
}

이 인의 런타임 | E | 표준 최단 경로보다 몇 배 더.

출처

2013-09-21 20:08:57 DanielV

Dijkstra의 최단 경로 알고리즘이 작동하지 않습니다.

답변

관련 문제