感谢各位读者厚爱，笔者的新书《供应链库存与计划管理》已经上架，并于本号设置内购。通过本公众号购买的读者，可以加入读者群交流，笔者将就书中内容知识，进行分享，讲解，不定期直播或录播。对疑问尽可能详细解答。
购书可点击以下（如书籍链接有问题可搜笔者闲鱼号 【林梦龙2024】 直接拍下即可或者私信联系笔者）
书籍目录可参考：
我的新书《供应链库存与计划管理：技术、方法与 Excel 应用》出版了
另外，由于一部分读者在笔者公布内购渠道前已经购买了，根据相应规则也可安排加入分享。
第一轮的分享课程开始陆续展开，参看：《供应链库存与计划管理》读者群分享课程内容
笔者曾经撰文分清楚旅行推销员和中国投递员的差异，并批评一些混乱的观点，详细见旅行推销员VS中国投递员 不是一个问题！解法演示！
这其中涉及到路径问题。
很多时候，特别物流网络层面等，寻找最短路径借此到达成本优化是常见的事情。以下将介绍其中的Dijkstra算法，内容均来自笔者的第二本新作，计划于明年上市，具体时间要看出版社的流程等。
Dijkstra算法是以其发现者E.W.Dijkstra（中文名译为戴克斯特拉）的名字命名，解决了从一个节点到目的地的最短路径的问题。
Dijkstra算法的做法就是从指定的某个节点（称为源节点）出发，寻找与它连结的所有节点之间的最短路径，并记录下来，一旦寻找到更短的路径时就更新。找到源节点与其他节点之间的最短路径之后，被找到的节点就会标记为“已访问”并添加在路径中。不断重复这个寻找过程，直到所有节点已经被访问，那么就可以得出从源节点到所有节点的最短路径了。
在Dijkstra算法中，权重是重要的概念，它可以表示距离，时间或者其他能够以节点之间的“连接”表示的概念。权重必须以正值表示，因为在计算过程中需要将边的权重相加寻找最短路径。如果具有负值的权重，意味着可能在后续的计算中得到总权重更小的路径，从而影响之前的结果。
图1是一个无向的具备权重的网络图，而源节点记为O，通过Dijkstra算法寻找出节点O到所有其他节点的最短路径。图中节点之间的数字为距离，表示为其权重。
▲ 图1 无向的具备权重的网络图
从开始的源节点O点到自身的距离为0，而源节点到其他节点的距离可以先行不作记录，因为并没有访问，而一旦访问过后，才更新数据到相应记录之中。
第一步，O出发，分别有O到A和O到C，其距离是2和6，那么OA是当中的最短路径，为此先对访问的点做记录，用删除线在表格中表示已经访问，然后在图中OA和OC虚线转为实线表示已访问，OA加粗表示最短路径，如图2。
▲ 图2 访问第一步
第二步，最短路径OA分别连接两个相邻的点，是B和C，其中C已经访问过，因此访问点B，由A到B的路径AB则为5，那么在B点的距离记录中，记录为7，因为源节点是O，OA+AB=2+5=7，所以更新记录如图3。不过B点除了连接A点外，尚有和C点连接，不清楚是否最短路径，所以暂不更新。
▲ 图3 访问第二步
第三步，B点和4个点相连接，分别是C,D,E,F，其距离分别是BC为2，BD为4，BE为6，BF为8，那么源节点O出发，O-C-B路径下OCB距离为6+2=8，多于OAB的7，因此到B的最短距离依然为7，所以AB是最短路径而线条加粗。而其他节点D,E,F均在此次访问，所以添加删除线表示已经访问。
此次连接中，到达D点，距离从源点O出发，则有OA+AB+BD=2+5+4=11。
此次连接中，到达E点，距离从源点O出发，则有OA+AB+BE=2+5+6=13。
此次连接中，到达F点，距离从源点O出发，则有OA+AB+BF=2+5+8=15。
这些一并更新记录如图4：
▲ 图4 访问第三步
第四步，E点的连接点有B,C,D,F其中B点路径已经访问，CE，DE和EF则分别是7，4和9，由于OAB是已经测量从源节点O到B的最短距离，而E节点除了连接C之外，不管连接D和F节点，都经由B节点，因此只需要考虑和连接C节点的比较。那么从源头O出发，由E的相邻节点而到达E点的路径和距离分别有：
OCE=OC+OE=6+6=12，
OABE=OA+AB+BE=2+5+6=13
因此，OCE是到达E节点的最短路径，距离是13，为此更新数据到图5：
▲ 图5 访问第四步
第五步，D节点和F节点连接是4。和F节点相邻节点有B,D,E，其中OAB是到达B节点的最短路径，OCE则是到达E节点的最短路径，而D均和B节点，E节点相接，所以只需比较OABF和OCEF的距离。
其中OABF=OA+AB+BF=2+5+8=15，而OCEF=OC+CE+EF=6+6+9=21，那么OABF则是源节点到F的最短距离。
同时D节点和B,E,F相邻，B和E均由不同最短路径，为此比较OABD和OCED哪个是最短路径，其中OABD=OA+AB+BD=2+5+4=11，而OCED=OC+CE+ED=6+6+4=14，则OABD为源节点O到D节点的最短路径，距离为11。
所有记录更新到图6：
▲ 图6 访问第五步
至此，所有节点访问完毕，并求解出最短路径。假如要到节点F，那么OABF就是最短路径的选择，距离为15；假如要到节点D，那么OABD则是最短路径选择，距离为11。
Dijkstra算法利用权重来计算，通过节点连接的权重，寻找出总权重最小的路径，特别在运输配送，物流网络建立等，起着重要的作用。
点个在看你最好看
