社区微信群开通啦，扫一扫抢先加入社区官方微信群
社区微信群
什么是最短路径呢？ 考虑到带权路径图，我们把一条路径上经过的权值之和是该路径的路径长度或者是带权路径长度。
那么我来个案例，比如我们还是村庄之间修路，我们指定了一个村庄起点和终点，假如我们修路只能在由村庄之间修路的全部可能情况之中选择一种，也就是说我们想从我们指定的村庄开始修路，修到我们指定的目的地，我们找到那条开销最小的路径，也就是1权值最小。
相比最小生成树，是整个村庄之间修路开销最小，生成树是相对于全部的修路情况中得到的，最短路径又是从生成树中选择出来一条最小开销的路，最小开销的路径也许不仅仅就是一个。
现在引出问题，我们想比如在我们的村庄之间修路问题，我们想从任意一个村庄到其他村庄之间修路开销最小问题，也可以说是最短路径。 这个路径其实就是村庄之间的权值之和最短，也就是村庄之间修路的开销问题。
当然我们的问题很明显是针对带权图的。
现在我们一个大神叫Dijkstra 发了一个用自己名字命名的求单源最短路径算法。中文名叫狄克斯特拉。
我们求最短路径的过程分析：
首先我们是把全部的顶点集合分成2组， 一个集合是用来存放我们的最短路径上的顶点集合 ，另外一个是存放我们的非在最短路径上的顶点。
刚开始查询之前我们的第一个集合只有一个起点 第二个集合保存了除了起点以外的全部顶点
后面我们根据起点去第二个集合中找在最短路径上的顶点，如果找到我们就加入到最短路径顶点集合中去，并且把他从非最短路径顶点集合中移除掉，一直检测，直到全部在最短路径上的点加入到了最短路径缓存集合，我们就终止查找操作。
如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！
