欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

城市最短路径问题(图的深度遍历)

程序员文章站 2024-03-23 21:41:04
...


/*
*	城市地图--- 图的深度优先搜索
*	计算从1号城市到5城市之间的最短路径
*	深度优先搜索
*/
#include<iostream>
using namespace std;
int min = 999999;
int book[101], n, e[101][101];
void dfs(int cur, int dis) {	//cur表示当前城市编号,dis表示已经走过的路程
	int j;
	if (dis > min)	//如果当前走过的路程已经大于之前找到的最短路程,则没有必要在尝试下去了,立刻返回
		return;
	if (cur == n) {	//判断是否到达了目标城市
		if (dis < min) {//如果该路程小,更新min
			min = dis;
		}
		return;
	}
	for (j = 1; j <= 5; j++) {//从1号城市到n号城市依次尝试
		if (e[cur][j] != 999999 && book[j] == 0) {
			book[j] = 1;		//标记城市已经在路径中
			dfs(j,dis+e[cur][j]);//从城市j再出发,继续寻找目标城市
			book[j] = 0;		//之前探索完之后,取消对城市j的标记
		}
	}
	return;
}
int main() {
	
	int i, j, m, a, b, c;//a,b 表示城市 c 表示之间的距离,m表示总的道路
	scanf("%d%d",&n,&m);
	//初始化二维矩阵
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) {
			if (i == j)
				e[i][j] = 0;
			else 
				e[i][j] = 999999;
		}
	}
	//读入该城市之间的道路
	for (i = 1; i <= m; i++) {
		scanf("%d%d%d",&a,&b,&c);
		e[a][b] = c;
	}
	//从1号城市出发
	book[1] = 1;//标记1号城市已经在路径中
	dfs(1,0);	//1表示当前城市的编号,0表示已经走过的路程
	printf("最短路径为:%d\n",min);
	return 0;
}

 

相关标签: d