最短路径(广度优先搜索)

广度优先搜索适用于所有边的权值相同的情况

当所有边的权值相同，采用BFS时，当找到终点，直接退出。
这时，得到的便是最短路径

一个案例：

各边权值均为1，找到1到5距离最小值

#include<stdio.h>

struct note
{
	int x;	//城市编号
	int s;	//转机次数
};
int main()
{
	struct note que[2501];	//形成一个队列
	int e[51][51] = { 0 };
	int book[51] = { 0 };	//标记这个点是否走过
	int head, tail;
	int i, j, n, m, a, b, cur, start, end, flag = 0;
	scanf("%d%d%d%d", &n, &m, &start, &end);

	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= n; j++)
		{
			if (i == j)
				e[i][j] = 0;
			else
				e[i][j] = 99999;
		}
	}

	for (i = 1; i <= m; i++)
	{
		scanf("%d%d", &a, &b);
		e[a][b] = 1;
		e[b][a] = 1;
	}

	head = tail = 1;	//队列初始化

	//从start号城市出发，将start号城市加入队列
	que[tail].x = start;
	que[tail].s = 0;
	tail++;		//因为已经有个start加入了队列，所以tail++
	book[start] = 1;	//标记start已在队列总

	while (head < tail)	//当队列不空时，循环
	{
		cur = que[head].x;
		for (j = 1; j <= n; j++)
		{
			//判断cur到j是否有路，且j还有没有被访问过
			if (e[cur][j] != 9999999 && book[j] == 0)
			{
				que[tail].x = j;	//下一个点转移到j
				que[tail].s = que[head].s + 1;	//路径+1
				tail++;	//因为有一个点加入了队列，因此tail++
				book[j] = 1;	//标记j加入了队列
			}
			if (que[tail].x == end)	//如果到达了终点，直接跳出
			{
				flag = 1;
				break;
			}
		}
		if (flag == 1)
			break;
		head++;	//必须是一个点扩展完毕之后，才有head++
	}
	//只要到达终点，此时的距离就是最小的
	printf("%d", que[tail - 1].s);	
	return 0;
}