图的深度优先遍历求最短路径( 二 ) _顶点

<< endl;int e1 = 0, e2 = 0, weigth = 0;for (int i = 1; i <= edge; i++){cin >> e1 >> e2 >> weigth;e[e1][e2] = weigth;}}//打印void Print(){for (int i = 1; i <= vertice; i++){for (int j = 1; j <= vertice; j++){cout << e[i][j] << "";}cout << endl;}cout << endl;}//dfs-求最短路径核心思想void dfs_minpath_Alg(int current,int distance,int goal)//current是当前节点编号，distance为已经走过的距离{int j = 0;if (distance > min)//如果此次已经走过的距离大于min最短路径，则没有必要继续探索下去{return;}if (current == goal)//已经走到目标城市{if (distance < min)//更新最小值{min = distance;}return;}for (int k = 1; k <= vertice; k++)//将所有节点依次遍历{//判断当前城市current到城市k是否有路，并判断城市k是否在已经走过的路径中if (e[current][k] != INT_MAX && current != k && book[k] == 0){book[k] = 1;dfs_minpath_Alg(k, distance + e[current][k], goal);//从城市k再出发，继续寻找目标城市book[k] = 0;//之前一步探索完毕之后，取消对城市k的标记}}return;}int Print_minPath(){return min;}};int main(){DFS_Traverse dfs(5, 8);dfs.Init_tu();dfs.GetEdgeInfo();cout << "初始信息：" << endl;dfs.Print();//dfs.dfs_Alg(1);cout << "最短路径(顶点1到5顶点)：" << endl;dfs.dfs_minpath_Alg(1, 0, 5);cout << dfs.Print_minPath() << endl;return 0;}