锐客网

  1. 首页 > it技术 > >

简谈迪克斯特拉算法

一、前言 一直想要学点简单的算法，叨叨了好久，开始吧【这篇文章的前言无非就是我想说点废话，大家可以选择性的过滤哈。】
二、概述 迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
【简谈迪克斯特拉算法】敲黑板~进入正题
迪杰斯特拉算法是目前OIER们最爱用的最短路算法，下面讲一下这个算法的思路【图丑，请大家忍耐一下】：

简谈迪克斯特拉算法
文章图片
例图
第一步，我们先把a加入集合，数组变成（s = {a}, dis[] = {0, ∞,∞,∞,∞,∞,∞,∞}）
第二步，找到和a最近的点，为b，把b加入集合，并确定他的最短路径【要注意箭头方向哈】，数组变成（s = {a, b}, dis[] ={0,2,∞,∞,∞,∞,∞,∞}）
第三步，找到和b最近的点，为d，把d加入集合，并确定他的最短路径【要注意箭头方向】，数组变成（s = {a, b, d}, dis[] = {0,2,∞,3,∞,∞,∞,∞}）
第四步，找到和d最近的点，为e，把e加入集合，并确定他的最短路径【要注意箭头方向】，数组变成（s = {a, b, d, e}, dis[] = {0,2,∞,3,5,∞,∞,∞}）
第五步，找到和e最近的点，为f，把f加入集合，并确定他的最短路径【要注意箭头方向】，数组变成（s = {a, b, d, e, f}, dis[] = {0,2,∞,3,5,9,∞,∞}）
第六步，找到和f最近的点，为g，把g加入集合，并确定他的最短路径【要注意箭头方向】，数组变成（s = {a, b, d, e, f, g}, dis[] = {0,2,∞,3,5,9,12,∞}）
第七步，目前只剩下c和h了，那么我们先要找到距离集合路径最短的c，把c加入集合，并确定他的最短路径，数组变成（s = {a, b, c, d, e, f, g}, dis[]= {0,2,13,3,5,9,12,∞}）
第八步，最后一步，我们找到距离集合路径最短的h，把h加入集合，并确定他的最短路径，数组变成（s = {a, b, c, d, e, f, g, h}, dis[] = {0,2,13,3,5,9,12,18}）
得嘞，这个大致的思路是这样的，还有后续哟，欲知后事如何，请看下回讲解~

    推荐阅读


    上一篇：〔117〕尿床

    下一篇：还有书读真好