最短路径（一）——dijkstra

	步骤	已用点	路径(A->B:权值)	最短路径	未用点B（遍历点）
1	设置矩阵weight，记录各点间距离(M为不可到达)，设置起始点start，weight[start][i]记录start到各点的最短距离，shortpath[i]记录最短路径，shortpath[start]默认为0			0->0:0	0，1，2，3，4
2	让start=0，0作为原点，标为已用，用bool[0]=1表示，比较0到其他未用点的距离，选取其中权值最小的路径作为一条最短路径（权值最小，不可能有通过其他点到达该点权值更小的路径），得到最短路径顶点为3	0	0->1:13 0->2:M 0->3:6 0->4:11	0->3:6	1,2,3,4
3	获取通过3到其他各点的距离，与原weight[start][i]中值比较，使weight[start][i]中均为start到各点的最短距离，再次比较weight[start][i]中除到0，3点的最小值，获得第三条最短路径，路径顶点为4	0,3	0->3->1:M(0->1:13) 0->3->2:23（0->2:M） 0->3->4:10(0->4:11)	0->3->4:10	1，2，4
4	重复步骤3	0，3，4	0->3->4->1:19(0->1:13) 0->3->4->2:13(0->3-2:23)	0->1:13 (此处到1，2距离相等，应均为最短路径，但为了代码方便，选其中一条路径)	1，2
5	重复步骤3	0，1，3，4	0->1->2:16(0->3->4->2:13)	0->3->4->2:13	2
6	获得所有最短路径，可输出（遍历完所有点）	0，1，2，3，4

对应图：

对应代码：

　　　　　　　　　static int M=10000; //不可到达，不可设置为int类型最大值，否则下面相加时会出错      
               public static void main(String[] args){
                           //设置一个图
                 int[][] weigth={
                            {0,13,M,6,11},//V0到V0,V1,V2,V3,V4
                           {13,0,3,M,9},//V1到V0,V1,V2,V3,V4
                            {M,3,0,17,3},
                            {6,M,17,0,4},
                            {11,9,3,4,0}
                  };
                  //起始点start
                 int start=0;
          
                 //最短路径：
                 dijkstra(weigth,start);
             }    
              private static void dijkstra(int[][] weigth, int start) {
                  int len=weigth.length;//顶点数
                  int[] distance=new int[len];//从start点到其他点的最短距离
                  String[] shortpath =new String[len];//从start到其他顶点的最短路径
                 
                  int[] bool=new int[len];//标记是否已收纳最短路径
                 bool[start]=1;
                  int k=-1;
                  distance[start]=0;
                 for(int i=0;i<len;i++){
                      shortpath[i]=start+"->"+i;
                  }
                 
                 for(int count=1;count<len;count++){
                     int minpath=Integer.MAX_VALUE;
                     for(int j=0;j<len;j++){
                          if(bool[j] !=1 && weigth[start][j]<minpath){
                              k=j;
                              minpath=weigth[start][j];
                         }
                      }//求start到其余各点中权值最小的点
                      bool[k]=1;//标记已使用点{0，k}
                      distance[k]=minpath;//获得点0到点k的最小距离
                      for(int i=0;i<len;i++){
                          if(bool[i]!=1 && minpath+weigth[k][i]<weigth[start][i]){
                              shortpath[i]=shortpath[k]+"->"+i;
                              weigth[start][i]=minpath+weigth[k][i];
                          }
                      }//求start->k->其余各点的距离，若小于start->其余各点距离，将weigth[start][i]设为那个更小的距离，shortpath记录经历的路径
                      
                 }
                  
                  //显示输出
                  for(int i=0;i<len;i++){
                      System.out.println("从"+start+"到"+i+"的最短路径为："+shortpath[i]+";最短距离为:"+distance[i]);
                  }
                 
              }

运算结果：

从0到0的最短路径为：0->0;最短距离为:0
从0到1的最短路径为：0->1;最短距离为:13
从0到2的最短路径为：0->3->4->2;最短距离为:13
从0到3的最短路径为：0->3;最短距离为:6
从0到4的最短路径为：0->3->4;最短距离为:10