Beej's Bit Bucketa day agoDijkstraalgorithmshortest pathhttp://beej.us/blog/data/dijkstras-shortest-path/Copy Link迪杰斯特拉算法用于在具有非负边权的图中寻找节点之间的最短路径。该算法维护一个未访问城市的集合，除起点距离设为0外，其余距离初始化为无穷大。它反复选择已知距离最小的未访问城市，并松弛其相邻城市。若通过当前城市找到更短的路径，松弛操作会更新邻居的距离和父指针。到达目标后，父指针可回溯出从起点出发的最短路径。该算法无法处理负边权，因为它假设后续不会找到更短的路径。边权可根据现实约束进行调整，例如轮渡路线、自行车道或陡峭道路。