dijkstra实现

单源最短路径问题，指定连接关系graph，源点src和节点总数V，每次选择从源点出发的能够到达的最近的节点u加入集合S中，u的加入可能会导致集合S中的节点最短路径发生变化，进行更新。
当剩余的V-1个节点全都更新完毕后，算法结束。

 public static int[] dijkstra(int graph[][], int src, int V) {
        int[] dist = new int[V];
        Boolean sptSet[] = new Boolean[V];
        for (int i = 0; i < V; i++) {
            dist[i] = Integer.MAX_VALUE;
            sptSet[i] = false;
        }
        dist[src] = 0;
        // 只需要对除了src外的N-1的节点全都遍历一次就可以了
        for (int count = 0; count < V - 1; count++) {
            int u = minDistance(dist, sptSet, V);
            sptSet[u] = true;
            // 由于集合发生了变化，那么从节点到源点的距离dist也可能发生变化
            for (int v = 0; v < V; v++)
                // 本来v没有被遍历过的，但是通过加入u之后，源点有了一条可到v的路径，并且源点通过u到达v比直接到达v更短，那么更新源点到v的距离，注意这里只是更新集合S中的节点的最短路径
                if (!sptSet[v] && graph[u][v] != -1 &&
                        dist[u] != Integer.MAX_VALUE &&
                        // 新加入的节点使得原来源点到v的距离发生了变化，那么进行更新，注意是对全部节点都更新，因为可能新节点的加入使得某些节点可达了
                        dist[u] + graph[u][v] < dist[v])
                    dist[v] = dist[u] + graph[u][v];
        }
        return dist;
    }

    // 每次选择一个距离源点最近的点加入集合（注意，是距离源点最近的节点），重复该函数，直到所有顶点都包含在集合中
    public static int minDistance(int dist[], Boolean sptSet[], int V) {
        int min = Integer.MAX_VALUE, min_index = -1;
        for (int v = 0; v < V; v++)
            if (sptSet[v] == false && dist[v] <= min) {
                min = dist[v];
                min_index = v;
            }
        return min_index;
    }