如何用C语言算法计算无向图中两点间的最短路径？

本文共计1176个文字，预计阅读时间需要5分钟。

1. 简介：无向图是图结构的一种。本次程序利用邻接表实现无向图，并通过广度优先遍历找到两点之间的最短路径。

2.广度优先遍历：广度优先遍历（BFS）和深度优先遍历（DFS）是图结构中常用的遍历方法。BFS和DFS都是找到两点之间最短路径的有效方法。

1.简介

无向图是图结构的一种。本次程序利用邻接表实现无向图，并且通过广度优先遍历找到两点之间的最短路径。

2.广度优先遍历

广度优先遍历(BFS)和深度优先遍历(DFS)是图结构中最常用的遍历方式。其中广度优先遍历配合上队列能够找到两点之间的最短路径，同时也能解决一些其他的问题(比如寻找迷宫的最短逃离路线)。广度优先遍历寻找两点之间最短路径的操作分为以下几步:

1）.首先定义起始点和终点src和dst。接着定义一个数组distance[ ]，用于存放各点到src的距离。初始化时各点到src的距离是INF(表示正无穷。这里可自行定义，作用是表示还未得到该结点到src的距离)，而distance[src] = 0。然后将src放入队列。

2）.取出队列的第一个结点(一开始队列只有src，这里就是取出src)放在变量top中；

3）.获得该结点的所有邻接结点，并且判断distance[ ]数组中各个邻接结点是否为INF。如果是说明还没有访问过该结点则将distance[ ]相应的位置设定为distance[top] + 1。如果不为INF，则表示之前已经访问过了，因此跳过。

4）.重复2-3步直到top变量等于dst为止。或者一直到队列为空，这种情况下说明两点间不存在路径。