Алгоритм Дейкстры с использованием матрицы смежности Проблема

Question

'пытается найти кратчайший путь между первым и последним узлом. Проблема заключается в том, что мой код всегда возвращает 0. У меня такое чувство, потому что оно вычисляет расстояние между первым узлом и первым узлом, которое стремится к нулю, но я не 100%. Почему мой код всегда возвращает 0?

Матрица adj [10] [10] и все узлы соединены, а g.network [] [] - матрица.

private static int dijkstras(Graph g) { 
    // Dijkstra's Algorithm 
    int[] best = new int[g.network.length]; 
    boolean[] visited = new boolean[g.network.length]; 
    int max = 10000; // Infinity equivalent. 
    for (int i = 0; i < g.network.length; i++) 
    { 
     best[i] = max; 
     visited[i] = false; 
    } 

    best[0] = 0; 

    for(int i = 0; i < g.network.length; i++) 
    { 
     int min = max; 
     int currentNode = 0; 
     for (int j = 0; j < g.network.length; j++) 
     { 
      if (!visited[j] && best[j] < min) 
      { 
       currentNode = j; 
       min = best[j]; 
      } 
     } 
     visited[currentNode] = true; 
     for (int j = 0; j < g.network.length; j++) 
     { 
      if (g.network[currentNode][j] < max && best[currentNode] + g.network[currentNode][j] < best[j]) 
      { 
       best[j] = best[currentNode] + g.network[currentNode][j]; 
      } 
     } 
    } 
      return best[g.network.length - 2]; 
} 

Answer 1

Я думаю, что, возможно, решить эту проблему, путем изменения кода следующим образом (я теперь переходящий в начальной точке вместо жесткого закодировано в «0»):

private static int dijkstras(Graph g, int start) // Added a start point. 
    { 
    // Dijkstra's Algorithm 
    int[] best = new int[g.network.length]; 
    boolean[] visited = new boolean[g.network.length]; 
    int max = 10000; // Infinity equivalent. 
    for (int i = 0; i < g.network.length; i++) 
    { 
     best[i] = max; 
     visited[i] = false; 
    } 

    best[start] = start; // Changed the 0 to variable start. 

    for(int i = 0; i < g.network.length; i++) 
    { 
     int min = max; 
     int currentNode = 0; 
     for (int j = 0; j < g.network.length; j++) 
     { 
      if (!visited[j] && best[j] < min) 
      { 
       currentNode = j; 
       min = best[j]; 
      } 
     } 
     visited[currentNode] = true; 
     for (int j = 0; j < g.network.length; j++) 
     { 
      if (g.network[currentNode][j] < max && best[currentNode] + g.network[currentNode][j] < best[j]) 
      { 
       best[j] = best[currentNode] + g.network[currentNode][j]; 
      } 
     } 
    } 
      return best[g.network.length - 2]; 
} 

я побежал этот код через цикл for и voila .... не только нуль возвращается.

Answer 2

Я прочитал ваш код, и я почти уверен, что это правильный алгоритм Дейкстры, так что я думаю, что, может быть, у вас есть нулевой путь между вашим первым узлом и последним узлом.