找最短路径問題

Question

   可以用dijkstra算法
 public static void dijkstra(boolean[] visted, int[] dist, int[][] map, int x) {
           Arrays.fill(visted, false);
           Arrays.fill(dist, Integer.MAX_VALUE);   visted[x] = true;   // 初始化dist数组
        for (int i = 1; i < dist.length; i++) {
            if (!visted[i] && map[x][i] != 0) {
                dist[i] = map[x][i];
          }
      }   while (true) {    int temp = 0;
          int min = Integer.MAX_VALUE;
   
         for (int i = 1; i < dist.length; i++) {
            if (dist[i] < min && !visted[i]) {
            min = dist[i];
             temp = i;
        }
   }
   // x = temp;
   if (temp == 0)
    break;
   visted[temp] = true;
        for (int i = 1; i < dist.length; i++) {     if (!visted[i] && map[temp][i] != 0
                && dist[i] > dist[temp] + map[temp][i]) {
                dist[i] = dist[temp] + map[temp][i];
    }
   }// for (int i : dist) {
         // System.out.print(i + " ");
      // }
  }
 } 

Answer 1

package com.hustbaidu.stwolf.JavaLearning.Introduction;public class Path { public static void main(String[] args) { int matrix[][] = { { 1000, 3, 10, 1000, 1000 },
{ 3, 1000, 1000, 5, 1000 }, { 10, 1000, 1000, 6, 15 },
{ 1000, 5, 6, 1000, 4 }, { 1000, 1000, 15, 4, 1000 } }; int n = 5; // number of node, node0...node4
int source = 1; // start node // initialize the distance from source to each vertex to infinity
int[] dist = new int[n]; for (int i = 0; i < n; i++) {
dist[i] = 1000; // infinity
}
// initialize every vertex as uned
boolean[] ed = new boolean[n];
// memset(&ed, 0, sizeof(ed)); // the distance from the source to the source is defined to be 0
dist[source] = 0; // we determine the shortest path to one vertex each iteration, there
// are n verticies so we loop n times.
for (int i = 0; i < n; i++) {
// find the closest uned node
int best = i;
for (int j = i; j < n; j++) {
if (matrix[i][j] < matrix[i][best]) {
best = j;
}
} //  the node, d[best] is the shortest path from source to best
ed[best] = true; // relax each of it's neighboors. See if it's shorter to get to j by
// going through best.
for (int j = 0; j < n; j++) {
dist[j] = Math.min(dist[j], dist[best] + matrix[best][j]);
}
} // dist[i] is the shortest path from source to i
for (int i = 0; i < dist.length; i++) {
System.out.println("" + source + " -> " + i + " : " + dist[i]);
}
}
}
/* Output:
1 -> 0 : 3
1 -> 1 : 0
1 -> 2 : 11
1 -> 3 : 5
1 -> 4 : 9
*/