BFS 수정

Question

모든 경로의 값이 1 인 모든 최단 경로를 찾으려고합니다. 수정 된 BFS를 사용했습니다. 닫힌 노드도 대기열에 추가하고있었습니다. 끝 노드를 찾으면 노드 추가를 멈추고 큐의 끝 노드를 계산합니다. 하지만 그것은 내 테스트 입력을 위해 작동하지 않습니다. 왜 내 생각이 나쁜거야? 여기에 의사

addIntoQueue(startNode) 
while(!queueIsEmpty()){ 
    nodeMain = dequeue() 
    if(nodeMain==stopNode){ 
     found=true 
     count++ 
    } 
    if(!found) 
    for(all node in NodeNeighbors){ 
     if(node!=CLOSED){ 
     addToQueue(node) 
     } 
    } 
    nodeMain=CLOSED 
} 

Answer 1

코드에서 몇 가지 문제가 있습니다 :

1. 무한 루프 : 소스에서 어떤 경로의 경우 대상에 -하지만주기가 그래프에있다, 귀하의 알고리즘은 0을 반환해야합니다 - 그러나 무한 루프에 머물러 있습니다.
2. 계산 잘못된 경로 :이의이 target를 가정 해 보자는 source에서 깊이 4에 있고, 경로 source->v1->v2->target 도달한다. 이제 그래프에 source->v3->v4->v5->target 경로가 있고 어떤 이유로 v4이 target 전에 대기열에 삽입되었다고 가정합니다 (두 경우의 순서에는 제한이 없습니다).

은이 그래프를 보라 ...하지만 당신은 그것을 계산 않았다 - 당신은 또한 가장자리 (v5,target)의 큐에 다시 target를 추가하고 또한 경로 source->v3->v4->v5->target를 계산하지만, 이것은 최단 경로가 아닌 것 예 :

위의 경우 먼저 s에서 시작하여 모든 인접 항목을 대기열에 추가합니다. 이제 (.. 아무것도 할 수없는없는, 그런 일이 가능)의이 v1 전에 v2가 추가됩니다 가정하자
이제 다음 단계에서, v2 확대 될 것입니다 그리고 당신은 큐에 v3을 추가합니다.
다음으로 v1이 처리되고 target이 큐에 추가됩니다.
이제 v3이 처리되고 target을 큐에 다시 추가하십시오.
이제 target이 처리되고 count이 증가되고 플래그 found이 설정됩니다.
대기열이 아직 비어 있지 않습니다. 이제 target을 처리하고 count을 다시 늘리십시오.

결과적으로 완료되었을 때 - count == 2이지만 단 하나의 최단 경로 만 있습니다. 이는 s->v2->v3->t 경로도 계산했기 때문에 발생합니다.