JAVA最短路径代码

import java.util.LinkedList;
import java.util.List;


public class ShortestPaths {
     private static String showPath[] = { "", "", "", "", "", "" }; 
      
         // 返回图的最短路径 
         public static int[] getShortPath(int path[][]) { 
            LinkedList<Integer> savePath = new LinkedList<Integer>();// 用于保存已添加进来的节点 
            int mark = 1; 
             int shortestPath[] = new int[path.length]; 
             for (int i = 0; i < shortestPath.length; i++) { 
                 shortestPath[i] = -1; 
             } 
             savePath.add(new Integer(0)); 
             if (savePath.size() == 1) { 
                 int num = savePath.getLast().intValue(); 
                 int minIndex = 0; 
                 for (int j = 0; j < shortestPath.length; j++) { 
                     shortestPath[j] = path[num][j]; 
                     if (shortestPath[j] >= 0) { 
                         showPath[j] = "1-->" + (j + 1); 
                     } else { 
                         showPath[j] = "无通路"; 
                     } 
                 } 
                 minIndex = getAddIndex(savePath, shortestPath); 
                 savePath.add(minIndex); 
             } 
      
             if (savePath.size() > 1) { 
                 while (mark < 6) {// savePath.size()<6 当有不可到达的点是将要出现死循环 
                     int num = savePath.getLast().intValue(); 
                     int minIndex = 0; 
                     for (int j = 0; j < path.length; j++) { 
                         if (path[num][j] >= 0) { 
                             if (shortestPath[j] < 0) { 
                                 shortestPath[j] = path[num][j] + shortestPath[num]; 
                                 showPath[j] = showPath[num] + "-->" + (j + 1); 
                             } else { 
                                 if (shortestPath[num] + path[num][j] < shortestPath[j]) { 
                                     shortestPath[j] = shortestPath[num] 
                                             + path[num][j]; 
                                     showPath[j] = showPath[num] + "-->" + (j + 1); 
                                 } 
                             } 
                         } 
                     } 
                     minIndex = getAddIndex(savePath, shortestPath); 
                     if (minIndex > 0) 
                         savePath.add(minIndex); 
                     mark++; 
                 } 
             } 
      
             return shortestPath; 
         } 
      
         // 获得加入到保存路径的节点 
         public static int getAddIndex(List list, int num[]) { 
             int index = 0; 
             for (int i = 0; i < num.length; i++) { 
                 if (!list.contains(new Integer(i))) { 
                     if (num[i] > 0 && index == 0) { 
                         index = i; 
                     } 
                     if (num[i] > 0 && index > 0) { 
                         if (num[i] < num[index]) 
                             index = i; 
                     } 
                 } 
             } 
             return index; 
         } 
      
         public static void main(String[] args) { 
             int path[][] = { { 0, -1, 15, -1, -1, -1 }, { 2, 0, -1, -1, 10, 30 }, 
                     { -1, 4, 0, -1, -1, 10 }, { -1, -1, -1, 0, -1, -1 }, 
                     { -1, -1, -1, 15, 0, -1 }, { -1, -1, -1, 4, 10, 0 } }; 
             int shortestPaht[] = getShortPath(path); 
             for (int i = 0; i < shortestPaht.length; i++) { 
                 System.out.print("节点 1 到节点 " + (i + 1) + " 的最短距离是" 
                         + shortestPaht[i] + "/t"); 
                 System.out.println("路径为：" + showPath[i]); 
             } 
         } 
     }