专栏名称: labuladong
算法,编程,致力于把问题讲清楚!
今天看啥  ›  专栏  ›  labuladong

漫画:Dijkstra 算法解决最短路径问题

labuladong  · 公众号  ·  · 2021-01-21 11:50
转载自公众号:程序员小灰作者:蠢萌的小灰—————  第二天  —————如何遍历呢?第一层,遍历顶点A:第二层,遍历A的邻接顶点B和C:第三层,遍历顶点B的邻接顶点D、E,遍历顶点C的邻接顶点F:第四层,遍历顶点E的邻接顶点G,也就是目标节点:由此得出,图中顶点A到G的(第一条)最短路径是A-B-E-G:换句话说,就是寻找从A到G之间,权值之和最小的路径。————————————究竟什么是迪杰斯特拉算法?它是如何寻找图中顶点的最短路径呢?这个算法的本质,是不断刷新起点与其他各个顶点之间的 “距离表”。让我们来演示一下迪杰斯特拉的详细过程:第1步,创建距离表。表中的Key是顶点名称,Value是从起点A到对应顶点的已知最短距离。但是, ………………………………

原文地址:访问原文地址
快照地址: 访问文章快照