Блог

Я пытаюсь закодировать алгоритм Дейкстры, начиная с любой вершины, мне нужно показать расстояние и напечатать путь к узлам. Он работает для вершин 2,4 и 5, но для 1 и 3 он запутывается. Вероятно, это что-то глупо маленькое, но я этого не вижу.

 public static void main(String[] args)
{
    int INF = Integer.MAX_VALUE;
    int verticies = 5;
    int W[][] = {{INF,7,4,6,1},
    {0,INF,0,0,0},
    {0,2,INF,4,0},
    {0,0,0,INF,0},
    {0,0,0,1,INF}};

    int startNode = 1;
    dijkstra(W,verticies,startNode-1);

}

public static void dijkstra(int G[][],int n,int startnode)
{
    int INF = Integer.MAX_VALUE, nINF = Integer.MIN_VALUE;
    //int cost[MAX][MAX],distance[MAX],pred[MAX];
    //int visited[MAX],count,mindistance,nextnode,i,j;
    int cost[][] = new int[n][n];
    int distance[] = new int[n];
    int pred[] = new int[n];
    boolean visited[] = new boolean[n];
    int count=0, mindistance=0, nextnode=0,i,j;

    //pred[] stores the predecessor of each node
    //count gives the number of nodes seen so far
    //create the cost matrix
    for(i=0;i<n;i  )
        for(j=0;j<n;j  )
            if(G[i][j]==0)
                cost[i][j]=INF;
            else
                cost[i][j]=G[i][j];

    //initialize pred[],distance[] and visited[]
    for(i=0;i<n;i  )
    {
        distance[i]=cost[startnode][i];
        pred[i]=startnode;
        visited[i]=false;
    }

    distance[startnode]=0;
    visited[startnode]=true;
    count=1;

    while(count<n-1)
    {
        mindistance=INF;

        //nextnode gives the node at minimum distance
        for(i=0;i<n;i  )
            if(distance[i]<mindistanceamp;amp;!visited[i])
            {
                mindistance=distance[i];
                nextnode=i;
            }

        //check if a better path exists through nextnode
        visited[nextnode]=true;
        for(i=0;i<n;i  )
            if(!visited[i])
                if(mindistance cost[nextnode][i]<distance[i])
                {
                    distance[i]=mindistance cost[nextnode][i];
                    pred[i]=nextnode;
                }
        count  ;
    }

    //print the path and distance of each node
    for(i=0;i<n;i  )
        if(i!=startnode)
        {
            if(distance[i] == INF || distance[i] < 0){
                System.out.print("nNo edge exists between node " (startnode 1) " and node " (i 1));
            } else {
                System.out.format("nDistance of node %d = %d", (i   1), distance[i]);
                System.out.format("nPath = %d", (i   1));

                j = i;
                do {
                    j = pred[j];
                    System.out.format("<-%d", (j   1));
                } while (j != startnode);
            }
        }
}
  

Я не знаю точно, как, но вы каким-то образом попадаете INF в свои вычисления. Мое подозрение касается строки distance[i]=mindistance cost[nextnode][i]; , но это может быть не единственный виновник, я не проверял. Когда mindistance равно 1 (или больше) и стоимость равна Integer.MAX_VALUE , вы получаете арифметическое переполнение, и результат становится отрицательным. Дальнейшее поведение я не предсказывал, но оно не такое, как ожидалось.

Когда в двух местах, которые вы определяете INF , я меняю значение на 1 000 000, я получаю следующий вывод из вашей программы:

 Distance of node 2 = 6
Path = 2<-3<-1
Distance of node 3 = 4
Path = 3<-1
Distance of node 4 = 2
Path = 4<-5<-1
Distance of node 5 = 1
Path = 5<-1
  

Я считаю, что это правильно.

Как я узнал? Я вставил это утверждение в середину вашего внешнего цикла while:

         System.out.println("count "   count   " nextnode "   nextnode   " mindistance "   mindistance);
  

Когда он напечатал большое отрицательное число, я начал подозревать арифметическое переполнение. Пока вы не научитесь использовать отладчик, System.out.println() это ваш друг для отладки.