更新时间：2024-08-09 16:23
最短路径问题是组合优化领域的经典问题之一，它广泛应用于计算机科学、交通工程、通信工程、系统工程、运筹学、信息论、控制理论等众多领域。Dijkstra算法是经典的最短路径算法。
Dijkstra算法是经典的最短路径算法，其基本思想是：设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对vi∈V-S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v, …, vk，就将vk加入集合S中，并将路径v, …, vk , vi与原来的假设相比较，取路径长度较小者为最短路径，重复上述过程，直到集合V中全部顶点加入到集合S中。使用该算法找到的是全局最优的最短路径，在网络节点数量大、网络边数较多时，存在内存占用大、时间复杂度高等不足，并且Dijkstra算法不能很好地解决含必经点约束的最短路径问题。
可分成两个子问题，即单源最短路径问题和所有顶点对之间的最短路径问题。前者是找出从某一顶点出发到图中所有其他顶点的最短路径，主要算法有迪克斯彻算法等；后者是求图中每一对顶点之间的最短路径，主要算法有弗洛伊德算法等。
互联网技术和应用的不断发展，对当今网络通信流量的要求不断增大。流量大、速度快、费用低的传输方式是网络传输的关键。路径最短、代价最低的网络路由能够大大降低通信成本、节约网络资源，提高网络资源的利用率。
最短路径问题是交通分配中最基本的问题，是指一对节点之间的路径中总阻 抗最小的路径，几乎所有交通流分配方法都是以它作为一个基本子过程反复调用。