最短路径
最短路径之迪杰斯特拉算法(Dijkstra Algorithm)
今天我们主要看⼀个最短路径算法,迪杰斯特拉算法(Dijkstra Algorithm)。
这个算法的主要运⽤就是计算从某个源点开始到其他顶点的最短路径的算法。
什么是最短路径,什么⼜是源点,还有最短路径算法有啥⼦⽤呢?我们来⼀个⼀个的看
基础概念
什么是源点?
路径起始的第⼀个顶点称为源点(Source),最后⼀个顶点称为终点(Destination)。图下
图中,我们⽤红⾊标注出的就可以认为是⼀个路径(V0 ->V1 ->V4 ->V6 ->V8)的源点和终点,但不要有
误区,其实图中的任何⼀个顶点都可作为源点或者终点,源点与终点只是相对⼀条路径⽽⾔的。
什么是最短路径
对于⽆向图⽽⾔,从源点V0到终点V8的最短路径就是从源点V0到终点V8所包含的边最少的
路径。我们只需要从源点V0出发对图做⼴度优先搜索,⼀旦遇到终点V8就终⽌。我们可以具体来看看如
何得到⽆向图中源点V0到终点V8的最短路径。
第⼀步:遍历顶点V0: