城市地图--深度优先遍历最短路径

本文主要是介绍城市地图--深度优先遍历最短路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

城市地图–深度优先遍历最短路径

要求

求城市1到城市5最短路程?

思路

同样使用图的邻接矩阵存储法存储地图，注意这次是有向图。使用深度优先遍历求解。从城市1出发，有分叉，先沿一条路径走下去，遇到分叉也是先选择一条往下走，直到走到城市5，此时并不一定是最短路径，或无路可走，回退到分叉点沿另一条走，重复步骤，直到回到第一个分叉口，此时全部路已经走完了。一个小技巧，在到达的每一个城市上记录走过的路程。

代码

#include <stdio.h>#define N 6
#define M 6int a[N][M] = {{ 0 },{ 0,  0,  2, -1, -1, 10},     { 0, -1,  0,  3, -1,  7},     { 0,  4, -1,  0,  4, -1},     { 0, -1, -1, -1,  0,  5},   { 0, -1, -1,  3, -1,  0}      };int b[M] = {0};
int min = 99999999;void dfs(int cur, int sum) {//if (sum > min) return; // 如果之前走过的大于最短路，没必要再尝试了if (cur == 5) {printf("%d\n", sum);if ( sum < min ) {min = sum;}return;}for (int i = 1; i < M; i++) {if (a[cur][i] > 0 && b[i] == 0){b[i] = 1;dfs(i, sum+a[cur][i]);b[i] = 0;}}
}int main() {b[1] = 1;dfs(1, 0);printf("min: %d\n", min);return 0;
}

这篇关于城市地图--深度优先遍历最短路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---