내 dijkstras 알고리즘에 문제가 있습니까

Question

그래서 저는 몇 시간 동안이 작업을 해왔고 극도로 좌절했습니다. 나는 내가 뭘 잘못하고 있는지 이해하지 못한다.

저는 Dijkstra 's Algorithm을 사용하여 인접 행렬을 사용하여 소스 정점과 4 개의 다른 정점 사이의 최단 경로를 찾습니다. 배후의 아이디어는 5 개의 도시와 항공편이 그들 사이를오고가는 것이므로 가장 늦은 티켓 가격을 찾아야합니다.

나는 의사 코드에있는 내 책의 알고리즘을 따르고 있으며 다음 웹 사이트의 코드는 다음과 같습니다. http://vinodcse.wordpress.com/2006/05/19/code-for-dijkstras-algorithm-in-c-2/

문제는 웹 사이트의 중첩 for 루프에서 카운터 나는 1에서 시작하고, 나는이 999

예에서 변경되지 않은 첫 번째를 제외하고 소스 정점에서 모든 정점까지의 거리가 올바른지 이유, 믿고 :

현재 거리 : 999 220 0 115 130

선행 작업 : 0 3 0 2 2

원래의 버텍스를 변경하더라도 모든 거리가 동일합니다 - 변경되지 않은 첫 번째 버텍스를 제외하고. 0 105 0 0 0

어쨌든

, 도와주세요 : 나는 카운터 I를 0으로 변경하면

, 그것은 즉

현재의 거리, 모든 거리를 망쳐 놨어요. 다음은 관련 코드입니다. 이

if(adjecencyMatrix[v][i]>0) 

는 비교의 나머지처럼 adjecencyMatrix[v][i][0].ticketPrice와 함께 할 수

void Graph::findDistance(int startingVertex) 
{ 
    for(int i=0; i<MAX;i++) 
    { 
    currentDistance[i] = 999; 
    toBeChecked[i] = 1; 
    predecessor[i] = 0; 
    } 

    currentDistance[startingVertex]=0; 
    bool flag=true; 
    int v; 
    while(flag) 
    { 
    v=minimum(); 

    toBeChecked[v]=0; 

    for(int i=1; i<MAX;i++) //here is where i think im going wrong 
    { 
     if(adjecencyMatrix[v][i]>0) 
     { 
     if(toBeChecked[i]!=0) 
     { 
      if(currentDistance[i] > currentDistance[v]+adjecencyMatrix[v][i][0].ticketPrice) 
      { 
      currentDistance[i] = currentDistance[v]+adjecencyMatrix[v][i][0].ticketPrice; 
      predecessor[i]=v; 
      } 
     } 
     } 
    } 

    flag = false; 
    for(int i=1; i<MAX;i++) 
    { 
     if(toBeChecked[i]==1) 
     flag=true; 
    } 
    } 
} 

int Graph::minimum() 
{ 
    int min=999; 
    int i,t; 
    for(i=0;i<MAX;i++) 
    { 
    if(toBeChecked[i]!=0) 
    { 
     if(min>=currentDistance[i]) 
     { 
     min=currentDistance[i]; 
     t=i; 
     } 
    } 
    } 
    return t; 
} 

Answer 1

를 확인하지할까요? adjecencyMatrix[v][i]가 배열 인 경우

, 그것은 포인터로 변환지고, 그 포인터는 항상 다시 0보다 큰 배열 - 투 - 포인터 붕괴 파업 :