java使用Dijkstra算法实现单源最短路径
Dijkstra算法是解决单源最短路径问题的经典算法，该算法由荷兰计算机科学家Edsger W. Dijkstra于1959年提出。单源最短路径问题是指在图中找出从给定顶点到其它任一顶点的最短路径。
单源最短路径问题的最优子结构性质是指，如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径，那么P(k,s)必定是从k到s的最短路径。这意味着，如果我们已经知道从顶点i到k的最短路径和从k到s的最短路径，那么我们可以通过组合这两条路径来得到从i到s的最短路径。
Dijkstra算法的核心思想是按照各顶点与源点v间的路径长度的递增次序，生成到各顶点的最短路径。算法的步骤如下：
1. 初始化，设置源点v的距离为0，其他顶点的距离为∞。
2. 选择当前距离源点v最近的未标记顶点k。
3. 更新从源点v到k的距离，并标记k为已访问。
4. 重复步骤2、3，直到所有顶点都被标记为已访问。
java实现Dijkstra算法的代码如下：
```java
public class Dijkstra {
static int M = 10000; //(此路不通)
public static void main(String[] args) {
int[][] weight = {
{0, 3, 2000, 7, M},
{3, 0, 4, 2, M},
{M, 4, 0, 5, 4},
{7, 2, 5, 0, 6},
{M, M, 4, 6, 0}
};
int start = 0;
int[] shortPath = Dijsktra(weight, start);
for (int i = 0; i < shortPath.length; i++) {
System.out.println("从" + start + "出发到" + i + "的最短距离为：" + shortPath[i]);
}
}
public static int[] Dijsktra(int[][] weight, int start) {
int n = weight.length;
int[] shortPath = new int[n];
String[] path = new String[n];
int[] visited = new int[n];
for (int i = 0; i < n; i++) {
path[i] = new String(start + "-->" + i);
}
shortPath[start] = 0;
visited[start] = 1;
for (int count = 1; count <= n - 1; count++) {
int k = -1;
int dmin = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
if (visited[i] == 0 && weight[start][i] < dmin) {
k = i;
dmin = weight[start][i];
}
}
visited[k] = 1;
for (int i = 0; i < n; i++) {
if (visited[i] == 0 && weight[start][k] + weight[k][i] < weight[start][i]) {
weight[start][i] = weight[start][k] + weight[k][i];
path[i] = path[k] + "-->" + i;
}
}
}
return shortPath;
}
}
```
该算法的时间复杂度为O(n^2)，其中n是图中的顶点个数。该算法可以解决单源最短路径问题，但它不适合解决所有对之间的最短路径问题。如果需要解决所有对之间的最短路径问题，需要使用Floyd-Warshall算法。
