在博客上发表了求最短路的Dijkstra算法后，有很多同学对路径比较感兴趣。也就是说，他们不仅想知道最后的结果，也想知道结果是怎么来的。想想也是自己的坏习惯所致，浅尝辄止。重新把Dijkstra算法的思路整理一遍，正好也温故而知新。

   首先从图的遍历方式说起。在数据结构中，树的遍历方式有三种：先序遍历、中序遍历、后序遍历。图比树更为灵活，但是图的遍历方式只有两种：深度优先和宽度优先。

      Dijkstra在本质上则是宽度优先。

   那么怎么记录路径呢？用一个一维数组就可以了。记录从到当前点的上一个点就OK了，然后再回溯，就得出了路径了。

   代码如下：

import java.util.Arrays;public class Dijkstra {    private static final int inf=Integer.MAX_VALUE;//表示两个点之间无法直接连通    public static int[] dijkstra(int[][] graph,int n,int u){        int[] path=new int[n];        int dist[]=new int[n];        boolean s[]=new boolean[n];        Arrays.fill(s, false);        Arrays.fill(dist, inf);        int min,v;        for(int i=0;i
    
     0;j--){                System.out.printf("%d->",shortest[j]);            }            System.out.println(shortest[0]);        }        return dist;    }    public static void main(String[] args) {         int[][] W = {                     {  0,   1,   4,  inf,  inf,  inf },                    {  1,   0,   2,   7,    5,  inf },                    {  4,   2,   0,  inf,    1,  inf },                     { inf,  7,  inf,   0,    3,    2 },                    { inf,  5,    1,   3,   0,    6 },                     { inf, inf,  inf,   2,   6,    0 } };                                                                                       dijkstra(W, 6, 0);                                                                                }}
    

结果：

1:0->1

3:0->1->2

7:0->1->2->4->3

4:0->1->2->4

9:0->1->2->4->3->5

第一个数字表示最短路径，冒号后面的表示路径。配合里面的图看就很容易懂了。

注，用到的数据还是

最后说明一点，上面的找路代码是直接套用《图论算法理论、实现及应用》一书，并非我自己想出来的。贴到博客的目的只是为了让更多的人学到东西。