Dijkstra의 알고리즘이 하나의 네거티브 에지로 실패하는 예

Question

Dijkstra의 알고리즘이 올바른 출력을 생성하지 못하는 한 에지를 제외하고 모든 에지에 양의 가중치가있는 그래프를 생각하려고합니다.

나는 기쁜 마음으로 생각합니다.

편집 :
나는 카운터 - 예를 들어이 그래프를 본 적이 있지만 그 이유를 이해하지 않습니다. 버텍스 A이 큐에서 마지막으로 튀어 나와서 Relax()의 가장자리 인 A->E이됩니다. 그래서 경로 S->A->E은 올바른 경로 (그리고 주장했다으로하지 S->B->E)

감사

다 익스트라가 목표 노드를 확장에 종료

Answer 1

인, 선택됩니다. 또한 dijkstra (대기열 아님)에서 우선 순위 대기열을 사용하므로 비용이 가장 적은 노드를 확장 할 수 있습니다. 그래서 당신의 예에서 A는 결코 확장되지 않을 것입니다.

open list = [ S cost:0 ] // priortiy queue 
pop S out of open list 
    closed list = [ S cost:0 ] 
    open list = [ B cost:1 ; A cost:5 ] 
pop B out of open list 
    closed list = [ S cost:0 ; B cost:1 ] 
    open list = [ E cost:2 ; A cost:5 ] 
pop E out of open list 
// it's better to terminate when we reach the goal but if we don't 
// it doesn't make any difference we are going to find the shortest path 
// to other nodes 
    closed list = [ S cost:0 ; B cost:1 ; E cost:2 ] 
    open list = [ A cost:5 ] 
pop A out of open list 
    // there isn't any nodes that we can push to open list 
    closed list = [ S cost:0 ; B cost:1 ; E cost:2 ; A cost:5 ] 
    open_list = [] 

는 다 익스트라는 그것의 가장 짧은 경로를 찾을 수있다 가정하기 때문에 그것 확장에 폐쇄 목록에 노드를 밀어 넣습니다. 목표에 도달 할 때 종료하지 않더라도 폐쇄 목록에 있기 때문에 A를 확장하지 않습니다.