有向图的单源非负最短路径算法-dijkstra算法

dijkstra应用范围：O(N2)

图中各边权值非负。

最短路径在现实中应用很广，比如在地图上找出最短路径等，这个算法很重要。

算法思想很简单，它不是找特定节点対之间的最短路径，它是找出源节点到所有其他节点的最短路径。

怎么找呢？

所需额外参数：path[] 记录路径。 dist[] 记录路径长度， visited [] 标记已找到最短路径的节点。

第一步初始化，

将源节点visited标记为true, 并将其直连边长度，更新到dist[]数组。

其次要明白所有路径中最短的路径是哪一条？

肯定是源节点直连边（路径长度为1）中最短的那一条。

第二条呢？

必然是直连边或者第一条最短路径再扩一边中的最小边。

第N条呢？

如果我们把以求出最短路径的点标记为true，那么可以证明，下一条最短路径必然是true点再扩一条边中的最短边所组成的路径。

然后我们依次找下去，找N-1次，就可以找到源节点到所有目标节点的最短路径。

想要找出所有节点间的最短路径，变换源节点，重复N次即可。

重点在于理解链式路径反应。

下面给出Java代码，图用邻接矩阵存储：

public int minPath(int source, int target){
        if (source == target){
            System.out.println("(" + source + " " + target + ")");
            return 0;
        }
        int[] path = dijkstra(source);
        int result = 0;
        String way = "";
        while (-1 != path[target]){
            way = "(" + path[target] + " " + target + ") " + way;
            result += graph[path[target]][target];
            target = path[target];
        }
        System.out.println(way);
        return result;
    }
    private int[] dijkstra(int vertex){
       int[] path = new int[numVertices];
       boolean[] visited = new boolean[numVertices];
       int[] lenPath = new int[numVertices];

       // initial
       int neighbor = getFirstNeighbor(vertex);
       while (neighbor != -1){
           lenPath[neighbor] = graph[vertex][neighbor];
           neighbor = getNextNeighbor(vertex,neighbor);
       }
       for (int i = 0; i < numVertices; i++) {
           if (lenPath[i] == 0){
               lenPath[i] = 1000;
               path[i] = -1;
           }else{
               path[i] = vertex;
           }
       }
       visited[vertex] = true;

        // find min pathLen in unvisited vertex.
       for (int i = 0; i < numVertices-1; i++) {
           int min = vertex;
           for (int j = 0; j < numVertices; j++) {
               if (visited[j] == false && lenPath[j] < lenPath[min]){
                   min = j;
               }
           }
           if (min == vertex){
               return path;
           }
           visited[min] = true;
           for (int j = 0; j < numVertices; j++) {
               if (visited[j] == false && lenPath[j] > lenPath[min] + graph[min][j]){
                   lenPath[j] = lenPath[min] + graph[min][j];
                   path[j] = min;
               }
           }
       }
       return path;
    }