dijkstra-java.txt

Dijkstra算法是典型的最短路算法

package helloween.datastruct;

public class ShortestRoad {
 
 
 /**  5*5矩阵  */
 int[][] cost = {
   {0, 3, 10000, 6, 9},
   {3, 0, 5, 10000, 8},
   {10000, 5, 0, 15, 5},
   {6, 10000, 15, 0, 10000 },
   {9, 9, 5, 10000, 0},
 };

 public int[][] ss(int[][] cost){
  
  int[][] _short = cost;
  
  for(int k=0; k<cost.length; k++){
   for(int i=0; i<cost.length; i++){
    for(int j=0; j<cost.length; j++){
     if(i == j || i == k || j == k) continue;
     //if(j < i) continue;

     //if(cost[i][j] > cost[i][k] + cost[k][j] ){
     if(_short[i][j] > _short[i][k] + _short[k][j] ){

      _short[i][j] = _short[i][k] + _short[k][j];
      
      p("重新计算最短路径: 从 " + i + " 经 " + k + " 到 " + j + "; " + cost[i][j] + " < " + cost[i][k] + " + " + cost[k][i] + ", 最短路径: " + _short[i][j]);
      
     }
     else{
      p("=====");
     }
    }
   }
  }
  
  return cost;
 }
 
 public static void p(String s){
  System.out.println(s);
 }
 
 public static void p(int[][] _short){
  for(int i=0; i<_short.length; i++){
   System.out.print(i + ": ");
   for(int j=0; j<_short[i].length; j++){
    System.out.print(_short[i][j] + " ");
   }
   System.out.println();
  }
 }
 
 public static void main(String[] args){
  ShortestRoad r = new ShortestRoad();
  
  p(r.ss(r.cost));
 }
}