蓝桥杯 DFS 查找最短路径（简单）
问题描述如图，百度地图上有5个地点，各个地点间是单向的路径，试求出从1到5的最短路径。从图中可以得到一个5*5的二维矩阵，利用深度搜索算法，求出最短路径。
参考代码 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;
//用来记录从0到此顶点所用的最短路径
int[] dist = new int;
//用来记录到达他的最近顶点下标
int[] path = new int;
//目标定点下表,(5)下表为4
int end = 4;
//首先遍历0到所有顶点是否联通
for (int i = 0; i < map.length; i++){
//如果联通,dist记录他的权值,path记录到达他的最近顶点为0
if (map != 0) {
dist = map;
path = 0;
}else {//不连通,dist为最大值(为了方便后面更新他的权值),path为-1(为了后面更新录到达他的最近的顶点)
dist = Integer.MAX_VALUE;
path = -1;
}
}
//循环条件:end定点为被划分为确定最短路径的顶点
while (!check) {
int min = Integer.MAX_VALUE;
int nodes = 0;
//从没有确定最小值的顶点选择一个最小距离
for (int i = 0; i < check.length; i++) {
if (!check && dist < min) {
min = dist;
nodes = i;
}
}
//讲该顶点标记为已找到到达他最近的顶点
check = true;
//查询最小顶点到附近顶点最短路径
for (int i = 0; i < map.length; i++) {
if (map!=0) {//确保是通路状态。
//0-当前最短距离+当前顶点到附近顶点距离<0-附近顶点距离
if (dist + map < dist) {
dist = dist + map;
path = nodes;//更新到这个节点的最短顶点Path
}
}
}
}
//输出从0到目标定点所走的最短路径
//根据path倒序输出
int index = end;
System.out.print(index+" ");
while (index != 0) {
System.out.print(path+" ");
index = path;
}
}
}
https://blog.51cto.com/u_15470300/4862796
页:
[1]