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

缘起

【1】中我们介绍了如何使用dfs求解有向网中一个顶点到另一个顶点的最短路径. 而且不仅可以将最短路径求出来, 而且可以得到最短路径有几条. 而这里介绍的bfs求最短路径就只能求出最短的那一条, 而不能求出所有的最短路径了.

分析

本例以无向图为例，其实有向网是一样做的. 

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
#include "stdafx.h"
#include <iostream>
#include <queue>
#include <vector>
#pragma warning(disable:4996)
#define LOCAL
using namespace std;

const int MAX_V_NUM = 105;

struct Graph
{
	int n; // 顶点的实际数目
	vector<int> vertex[MAX_V_NUM]; // 邻接链表法

	typedef vector<int>::iterator it;
	
	struct Block
	{
		int len; // 到本节点为止的宽搜步数
		int v; // 顶点索引
		Block *parent; // 谁将我带入队列中
		Block(int len, int v, Block *parent):len(len),v(v),parent(parent){}
	};

	bool book[MAX_V_NUM]; // 标记有无加入队列. 对于已经加入队列的节点 就不要再次加入了

	Graph()
	{
		puts("输入顶点个数");
		scanf("%d", &n);
		puts("输入边");
		int x,y;
		while(~scanf("%d%d", &x, &y)) // 无向图
		{
			vertex[x].push_back(y);
			vertex[y].push_back(x);
		}
	}

	void bfs() // 本例依旧是写死从1到达5的
	{
		memset(book, 0, sizeof(book));
		book[1] = true;
		queue<Block*> q;
		q.push(new Block(0,1,0));
		Block *front;
		while(!q.empty())
		{
			front = q.front();
			if (front->v == 5) break; // 如果到达目的地
			q.pop();
			for (it x=vertex[front->v].begin(); x!=vertex[front->v].end();x++)
			{
				if (!book[*x]) // 如果尚未加入过队列
				{
					book[*x] = true;
					q.push(new Block(front->len+1,*x,front));
				}
			}
		}
		if (front->v!=5)
		{
			puts("不能到达5");
		}
		else
		{
			printf("1到达5的 最短距离是%d, 具体路径如下:\n",front->len);
			while(front->parent)
			{
				printf("%d <- ",front->v);
				front = front->parent;
			}
			puts(" <- 1");
		}
	}
};

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif
	Graph g;
	g.bfs();
	return 0;
}
/*
测试数据
5
1 2
1 3
2 3
2 4
3 4
3 5
4 5
*/

后记

这里必须要注意, bfs求最短路径只适用于边的权重为1（这本质上因为bfs步步为营，按先来后到顺序考察进队节点），并且不能求出所有的最短路径, 而只能求出一条. 而【2】中介绍的dfs求两点之间的最短路径则更为通用——不需要边的权为1就行. 其实对于【2】中的A*算法, 它也未必求出的是最短路径, 它只是牺牲准确性的情况下提升了搜索的效率——只是庆幸的是, 如果启发式函数构造的好, 其实近似解和最优解差距并不大. 甚至就是最优解. 真正精确的是dfs——毕竟dfs考察了所有的路. 而且为什么bfs求最短路的时候，对于别的节点已经考察过的不需要再次进队(代码第55行)? 因为之前已经考察过这个格点了（它曾经进过队）. 所以不需要再次开拓了（len只会增加，所以再开拓它没有任何意义，所以不需要再次进队）

参考

【1】https://yfsyfs.github.io/2019/05/27/%E4%BD%BF%E7%94%A8dfs%E6%B1%82%E8%A7%A3%E6%9C%89%E5%90%91%E7%BD%91%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84/

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