如何运用Dijkstra算法规划五一最省钱旅游路线？

本文共计2803个文字，预计阅读时间需要12分钟。

明天就是五一了，大家准备好旅游攻略了吗？今天小张带大家了解一篇关于文章，用Dijkstra算法帮你轻松搞定旅游路线，既实惠又省心，快来围观吧！案例：五一快到了，小张准备去旅游。

明天就是五一了，大家准备好旅游攻略了吗？今天小编带大家了解一篇关于文章，用dijkstra算法帮你轻松搞定旅游路线，实惠又省心，快来看看吧！

案例：

五一快到了，小张准备去旅游了！

查了查到各地的机票

　　
因为今年被扣工资扣得很惨，小张手头不是很宽裕，必须精打细算。他想弄清去各个城市的最低开销。

如果他想从珠海飞到拉萨，最少要花多少机票钱呢？下面就说到我们今天要说的这个算法。

迪杰斯特拉(Dijkstra)算法

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法的时间复杂度为O(N^2)。

扩展

狄克斯特拉Dijkstra1930年5月11日生于荷兰鹿特丹的一个知识分子家庭，在兄弟姊妹4人中排行第三。他的父亲是一名化学家和发明家，曾担任荷兰化学会主席。他母亲则是一位数学家。他成功地设计并实现了在有障碍物的两个地点之间找出一条最短路径的高效算法，这个算法被命名为“狄克斯特拉算法”，解决了机器人学中的一个十分关键的问题，即运动路径规划问题，至今仍被广泛应用。