无权有向图的最短路径_无权有向图求最短路径

为什么使用BFS就够了?

因为BFS的时候离src越近的点越早被访问(先进先出)。

代码：

#include<iostream>
#include<list>
#include<vector>
#include<queue>

#define INF 9999999			//无穷大 
#define NIL -1           
using namespace std;

class Graph
{
	int n;				//顶点数
	list<int>*adj;		//邻接表
public:
	Graph(int _n)
	{
		n = _n;
		adj = new list<int>[_n]; 
	} 
	~Graph(){ delete[] adj;}
	void addEdge(int u, int v)
	{
		adj[u].push_back(v);
	} 
	void unweightedShortestPath(int src);
};
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

void Graph::unweightedShortestPath(int src)
{
	vector<int>dist(n, INF);		//INF = 9999999
	vector<int>path(n, NIL); 		//NIL = -1
	queue<int>q;
	dist[src] = 0;	
	q.push(src);
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		list<int>::iterator it;
		for(it = adj[u].begin(); it != adj[u].end(); it++)
		{
			int v = *it;
			if(dist[v] == INF)
			{
				dist[v] = dist[u] + 1;
				path[v] = u;
				q.push(v); 
			}
		} 
	}
	
	//输出
	for(int i = 0; i < n; i++)
	{
		cout<<path[i]<<"--->"<<i<<"\t dist["<<i<<"] is :"<<dist[i]<<endl;
	} 
	cout<<endl;
} 
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

int main()
{
	Graph g(7);
	g.addEdge( 0, 1);
	g.addEdge( 0, 3);
	g.addEdge( 1, 3);
	g.addEdge( 1, 4);
	g.addEdge( 2, 0);
	g.addEdge( 2, 3);
	g.addEdge( 2, 5);
	g.addEdge( 3, 2);
	g.addEdge( 3, 4);
	g.addEdge( 3, 5);
	g.addEdge( 3, 6);
	g.addEdge( 4, 6);
	g.addEdge( 6, 5);
	
	g.unweightedShortestPath(0);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20