使用dfs求解有向网最短路径

缘起

我们学习过求最短路径的很多算法. dijkstra、bellman-ford、floyd等等. 但是别忘了，最基本的dfs也可以给我们求解最短路径. 而且如果你愿意,甚至可以求出所有最短路径来.

本文提供的程序实现需求是, 求出有向网中一个顶点到另一个顶点的最短路径.

分析

dfs 没什么好说的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include "stdafx.h"
#include <iostream>
#include <vector>
#pragma warning(disable:4996)
#define LOCAL
using namespace std;

const int MAX_V_NUM = 105;

struct Graph
{
	struct Edge
	{
		int v,w;
		Edge(int v, int w):v(v),w(w){}
	};

	typedef vector<Edge>::iterator it;

	int n, _min, minpath[MAX_V_NUM][MAX_V_NUM], minpathnum; // _min 是最短路径、minpath的每一行记录了一条最短路径, minpathnum记录了最短路径的条数, 
	vector<Edge> vertex[MAX_V_NUM];
	bool book[MAX_V_NUM]; // true表示已经被占用，false表示没有

	Graph()
	{
		puts("输入顶点的实际个数");
		scanf("%d", &n);
		puts("输入边的起点终点和权重");
		int x,y,w;
		while(~scanf("%d%d%d",&x,&y,&w)) vertex[x].push_back(Edge(y,w));
		memset(book, 0, sizeof(book));
		book[1] = true;
		_min = 0x3f3f3f3f;
		minpathnum = 0;
	}

	void dfs(int cur, int distance, int *path, int len) // cur是当前的顶点, distance是已经达到的距离，path用于记录路径，len是当前path中的索引
	{
		if (distance > _min) // 如果已经超了,则没必要进行下去了
		{
			return; // 剪枝
		}
		path[len] = cur; // 记录当前路径
		if (cur == 5) // 本例以目的地5为例
		{
			if (_min != distance) // 那么distance<_min, 则新的最小诞生了, 之前得到的最小都不能算数的
			{
				_min = distance;
				minpathnum = 1; // 重新统计了
				memcpy(minpath[0], path, (len+1)*sizeof(int));
				minpath[0][len+1] = 0; // 以0结尾, 则表示路径结束
			}
			else // 如果相等,表示最短路径条数+1
			{
				memcpy(minpath[minpathnum++], path, (len+1)*sizeof(int));
				minpath[minpathnum-1][len+1] = 0; // 0封尾
			}
		}
		for (it x = vertex[cur].begin(); x!=vertex[cur].end(); x++)
		{
			if (!book[x->v])
			{
				book[x->v] = true; // 锁定
				dfs(x->v, distance+x->w, path, len+1); // 注意, distance+x->w 而不能distance+=x->w, 因为在本轮中 distance是不能变的
				book[x->v] = false; // 解锁
			}
		}
	}
};

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif
	Graph g;
	int path[MAX_V_NUM];
	g.dfs(1,0, path, 0);
	printf("1到5最短距离是%d,一共%d条, 路径如下\n", g._min, g.minpathnum);
	for (int i = 0; i< g.minpathnum; i++)
	{
		int j = 0;
		while(g.minpath[i][j]) printf("%d ", g.minpath[i][j++]);
		puts("");
	}
	return 0;
}
/*
测试数据
5
1 2 2
2 3 3
3 4 4
4 5 5
1 5 10
2 5 7
5 3 3
3 1 4
*/

【1】中的 A* 寻路算法. 其实只是得到了一个近似的结果. 注意, 我们在

参考

【1】https://yfsyfs.github.io/2019/05/26/A-star-%E5%AF%BB%E8%B7%AF%E7%AE%97%E6%B3%95/