单源最短路径问题，指定连接关系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;
}
