[python] 蓝桥杯 DFS 查找最短路径（简单）

import java.util.ArrayList;
import java.util.Arrays;
public class 迪杰斯特拉 {
  //根据路径图写出连通图.0为不连通,若联通记录他的权值
static int[][] map = {
{0,2,0,0,10},
{0,0,3,0,7},
{4,0,0,4,0},
{0,0,0,0,5},
{0,0,3,0,0}
};
  //顶点
static int[] nodes = {1,2,3,4,5};

public static void main(String[] args) {
    //用来记录此顶点是否标记为确定最短路径的顶点
boolean check[] = new boolean[nodes.length];
    //用来记录从0到此顶点所用的最短路径
int[] dist = new int[nodes.length];
    //用来记录到达他的最近顶点下标
int[] path = new int[nodes.length];
//目标定点下表,(5)下表为4
int end = 4;
//首先遍历0到所有顶点是否联通
for (int i = 0; i < map.length; i++){
//如果联通,dist记录他的权值,path记录到达他的最近顶点为0
if (map[0][i] != 0) {
dist[i] = map[0][i];
path[i] = 0;
}else {//不连通,dist为最大值(为了方便后面更新他的权值),path为-1(为了后面更新录到达他的最近的顶点)
dist[i] = Integer.MAX_VALUE;
path[i] = -1;
}
}
//循环条件:end定点为被划分为确定最短路径的顶点
while (!check[end]) {
int min = Integer.MAX_VALUE;
int nodes = 0;
//从没有确定最小值的顶点选择一个最小距离
for (int i = 0; i < check.length; i++) {
if (!check[i] && dist[i] < min) {
min = dist[i];
nodes = i;
}
}
//讲该顶点标记为已找到到达他最近的顶点
check[nodes] = true;
//查询最小顶点到附近顶点最短路径
for (int i = 0; i < map.length; i++) {
if (map[nodes][i]!=0) {//确保是通路状态。
//0-当前最短距离+当前顶点到附近顶点距离<0-附近顶点距离
if (dist[nodes] + map[nodes][i] < dist[i]) {
dist[i] = dist[nodes] + map[nodes][i];
path[i] = nodes;//更新到这个节点的最短顶点Path
}
}
}
}
//输出从0到目标定点所走的最短路径
//根据path倒序输出
int index = end;
System.out.print(index+" ");
while (index != 0) {
System.out.print(path[index]+" ");
index = path[index];
}
}
}