思想:利用深度优先遍历;
① 定义一个全局变量min,用来实现每条路径的比较;
② 回溯法可以实现不同路径
【注】手动模拟代码,可更加直观
核心代码:
int min=9999999;
dfs(1,0) //1为顶点,0为当前顶点的路径长度
v[1]=1;//已访问
public static void dfs(int cur, int dis) {
/**
* 如果当前路径大于之前找到的最小值,可直接返回
* */
if (dis > min) {
return;
}
/**
* 判断是否达到最后一个结点,更新最小值,返回
* */
if(cur == n) {
if (dis < min) {
min = dis;
return;
}
}
/**
* 当前点到其他各点之间可连通但是还未添加进来时,遍历执行
* */
for (int i = 1; i <= n; i++) {
if (edge[cur][i] != Integer.MAX_VALUE && vertex[i] == 0) {
vertex[i] = 1;
dfs(i, dis+edge[cur][i]);
/**
* 回溯
**/
vertex[i] = 0;
}
}
return;
}