解决的问题是带权图中从顶点到其他各顶点的最短路径，这里主要说Dijkstra算法和Floyd算法。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13256.html
一、Dijkstra算法文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13256.html
1、定义描述文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13256.html
Dijkstra算法是典型的最短路径算法，用于计算图或网中某个特定顶点到其他所有顶点的最短路径，以起始点为中心向外层层扩展，直到扩展到终点为止，适合计算单源最短路径，时间复杂度是O(N^2)。用到的是贪心法。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13256.html
2、算法思想文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13256.html
设G=(V,E)是一个带权的有向图，把图中顶点集合V分成两组，第一组为以求出最短路径的顶点集合，(用S表示，初始时S中只有一个源点，以后没求得一条最短路径，就将其加入到集合S中，直到全部顶点都加入到S中，算法就结束了)，第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入到S中。在加入过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任意顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13256.html
二、Floyd算法文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13256.html
1、定义描述文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13256.html
Floyd算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的闭包。Floyd算法的时间复杂度是O(N^3)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13256.html
上图4个城市，8条公路，公路上的数字表示这条公路的长度，这些公路都是单向的，我们需求求任意两个城市之间的最短路程，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13256.html
这个问题被称为"多源最短路径"问题。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13256.html
2、算法思想文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13256.html
Floyd是个经典的动态规划问题。我们的目标是寻找从i到j的最短路径，从动态规划角度看，我们需要为这个目标重新做一个诠释，从任意点i到任意点j的最短路径不外乎两种可能，一是从i直接到j，二是从i经过若干节点k到j，所以我们假设Dis(i,j)为顶点u到顶点v的最短路径的距离，对于每个顶点k，我们看Dis(i,k) + D(k,j) > Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设Dis(i,j)=Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有顶点k，Dis(i,j)中记录的便是i到j的最短路径的距离。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13256.html
3、算法步骤文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13256.html
从任意一条单向边开始，所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13256.html
对于每个顶点u和v，看看是否存在一个顶点w，使得u到w再到v比已知的路径更短，如果是就更新它。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13256.html