package suanfa;
public class Main {
public static void main(String[] args) {
int max = Integer.MAX_VALUE-10000;
int graph[][] = {
{max,max,10,max,30,100},
{max,max,5,max,max,max},
{max,max,max,50,max,max},
{max,max,max,max,max,10},
{max,max,max,20,max,60},
{max,max,max,max,max,max},
};
dijkstra(graph);
}
public static void dijkstra(int[][] arr) {
// 保存每个节点的前驱，即从哪个节点走到当前节点去，path[1]=0表示从节点0走到1去
int[] path = new int[6];
// 到当前节点的最短开销 costs[5]=100表示当前最短路径到节点5的开销为100
int[] costs = new int[6];
// 对于确定了最短路径的节点赋值为true,没确定的false
boolean[] isCompleted = new boolean[6];
// 初始化节点0到各个节点的权值
for (int i = 0; i < 6; i++) {
costs[i] = arr[0][i];
if(costs[i]!=Integer.MAX_VALUE-10000){
path[i]=0;
}else{
path[i] = Integer.MAX_VALUE;
}
}
isCompleted[0] = true;
// 节点0的前驱节点是0
path[0] = 0;
for (int k = 1; k < 6; k++) {
// 找到以当前节点为起点的，到达其他节点距离最短的节点
int minIndex = -1;
int min = Integer.MAX_VALUE;
for (int j = 0; j < 6; j++) {
if (!isCompleted[j] && costs[j] < min) {
min = costs[j];
minIndex = j;
}
}
if(minIndex == -1) continue;
// 因为前面的路径是保证了最短路径的，所以遍历获取能到达的最小值显然也是最短路径
isCompleted[minIndex] = true;
for (int i = 1; i < 6; i++) {
//动态修改临时权值和路径
int value = arr[minIndex][i] + min;
if (!isCompleted[i] && value < costs[i]) {
costs[i] = value;
path[i] = minIndex;
}
}
}
System.out.println();
}
}
