Dijkstra의 알고리즘이 잘못된 값을 반환합니다.

Question

저는 Dijkstra의 알고리즘을 이해하려고 시도해 왔습니다. 간단히 말해 알고리즘은 A와 B 사이의 주어진 거리 사이의 최단 거리를 찾습니다.

알고리즘 버전을 게시하고 (노드 간 거리가 그다지 많지는 않습니다), 노드 간 거리를 게시합니다.

1 to 2 is 48

... 다음과 같이 내가 함께 일하고 있어요 값은

1 to 2 is 40

을해야 할 때 :

를

void GraphM::findShortestPath() 
{ 
    for (int i = 1; i <= nodeCount; i++) // From Node i... 
    { 
     for (int v = 1; v <= nodeCount; v++) // ...through Node v... 
     { 
      for (int w = 1; w <= nodeCount; w++) // ...to Node w 
      { 
       if (!T[i][w].visited || !T[i][v].visited) 
       { 
        T[i][w].dist = min(T[i][w].dist, T[i][v].dist + C[v][w]); 
        T[i][v].visited = true; 
        T[i][w].visited = true; 
       }   
      } 
     } 
    } 

    cout << "1 to 2 is " << T[1][2].dist << endl; 
} 

이

는 다음을 출력

1 2 50 
1 3 20 
1 5 30 
2 4 10 
3 2 20 
3 4 40 
5 2 20 
5 4 25 

... 각 행에서 첫 번째 토큰은 첫 번째 노드이고 두 번째 토큰은 두 번째 노드이며 세 번째 토큰은 해당 노드 간의 거리입니다 (알고리즘의 경우 이러한 토큰은 i, v 및 T [i] [v] .dist). 알고리즘에서 nodeCount는 그리드 (5)에있는 노드의 수이고, w는 i와의 거리를 찾고있는 노드입니다. C [v] [w]는 v와 w 사이의 원래 거리를 반환합니다. 따라서 v가 5이고 w가 2이면 C [v] [w]는 20을 반환합니다. 이것은 일정하지만 T [v] [w] .dist (예 :)는 변경할 수 있습니다.

C [5] [3] 또는 T [1] [4] .dist와 같은 존재하지 않는 노드 관계는 (적어도 처음에는) 무한대에 해당하는 INT_MAX를 반환합니다.

궁금한 분은 다음과 같이하십시오. 예, 이것은 과제물입니다. 불행하게도, 교수님은 구조체 T 사용과 같은 몇 가지 구체적인 세부 사항을 필요로했습니다. 그리고 다소 모호한 윤곽선 이외에 Dijkstra의 알고리즘을 코드에 작성하는 방법에 대해서는 자세히 설명하지 않았습니다. 나는 단순히 누군가가 내가하고있는 일과 가능하면 해결하는 법을 말할 수 있는지 묻는다.

도움을 주시면 벽에 머리를 대고 많은 시간을 절약 할 수 있습니다.

Answer 1

이것은 다이 즘 트라의 알고리즘이 아닙니다. 구현하고자하는 것은 Floyd-Warshall 알고리즘입니다. 이것은 모든 정점 쌍에 대한 최소 거리를 찾는다. 첫 번째 루프는 전송 노드를 통해 루프 것을

http://en.wikipedia.org/wiki/Floyd–Warshall_algorithm

참고. 이 구현을 사용하면 이미 방문한 가장자리를 기억할 필요가 없습니다.

void GraphM::findShortestPath() 
{ 
    // Initialize T[i][j] to C[i][j] or MAX_INT here 
    for (int k = 1; k <= nodeCount; k++) // Through Node k... 
    { 
     for (int u = 1; u <= nodeCount; u++) // ...From Node u... 
     { 
      for (int v = 1; v <= nodeCount; u++) // ...to Node v 
      { 
       // if going through k provides a cheaper path, update T[u][v] 
       T[u][v] = min(T[u][v], T[u][k] + T[k][v]);   
      } 
     } 
    } 

    cout << "1 to 2 is " << T[1][2]<< endl; 
}