最短路径的实现算法Dijkstra和Bellman-ford原理和java实现代码
一、最短路径问题基本知识
从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径叫做最短路径。最短路径问题主要有两种：单源最短路径问题和多源最短路径问题。
单源最短路径问题就是从一个点到所有其他点的最短路径,得到的结果是一个数组,表示某个点到其他点的最短距离。常用的算法有Dijkstra算法、Bellman-ford算法和SPFA算法。其中SPFA算法是Bellman-ford算法的队列优化。（给定一个带权有向图G=（V,E），其中每条边的权是一个实数。另外，还给定V中的一个顶点，称为源。要计算从源到其他所有各顶点的最短路径长度。这里的长度就是指路上各边权之和。这个问题通常称为单源最短路径 [1] 问题。）
多源最短路径问题计算所有点到其他点的最短距离,得到的是一个矩阵。常用的算法有Floyd-Warshall算法。Floyd-Warshall也可以解决单源路径问题，但效率比较低。
Dijkstra算法不能求带负权边的最短路径，而SPFA算法、Bellman-Ford算法、Floyd-Warshall可以求带负权边的最短路径。
Bellman-Ford算法的核心代码只有4行，Floyd-Warshall算法的核心代码只有5行。
二、单源路径问题算法：解决是给点一个源点，求这个源点到其他各点的最短路径
1、 Dijkstra算法：
1）又称迪杰斯特拉算法，是一个经典的最短路径算法，主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止，使用了广度优先搜索解决赋权有向图的单源最短路径问题，算法最终得到一个最短路径树。时间复杂度为O(N^2)。其中每条边的权是一个非负实数。
实例：
与最小生成树PRIM算法很类似
2）抽象步骤：
将起点A放入集合中，A点的权值为0,因为A->A=0。
与起点A相连的所有点的权值设置为A->点的距离，连接不到的设置为无穷。并且找出其中最小权值的B放入集合中（此时A->B必定为最小距离）。
与B点相连的所有点的权值设置为B->点的距离，并且找出其中最小权值的C点放入集合中（此时C的权值必定为其最小距离）。
重复步骤3，直至所有点加入集合中。便能得到所有点与A点的最短距离。
3）代码实现
2、 Bellman-Ford算法：其显著特点是可以求取含负权图的单源最短路径
1）算法概要：该算法由美国数学家理查德•贝尔曼（Richard Bellman, 动态规划的提出者）和小莱斯特•福特（Lester Ford）发明。Bellman-Ford算法的流程如下： 给定图G(V, E)（其中V、E分别为图G的顶点集与边集），源点s
2）算法思路：
数组Distant[i]记录从源点s到顶点i的路径长度，初始化数组Distant[n]为, Distant[s]为0
以下操作循环执行至多n-1次，n为顶点数： 对于每一条边e(u, v)，如果Distant[u] + w(u, v) < Distant[v]，则另Distant[v] = Distant[u]+w(u, v)。w(u, v)为边e(u,v)的权值； 若上述操作没有对Distant进行更新，说明最短路径已经查找完毕，或者部分点不可达，跳出循环。否则执行下次循环；
为了检测图中是否存在负环路，即权值之和小于0的环路。对于每一条边e(u, v)，如果存在Distant[u] + w(u, v) < Distant[v]的边，则图中存在负环路，即是说改图无法求出单源最短路径。否则数组Distant[n]中记录的就是源点s到各顶点的最短路径长度。
3）代码实现：
![在这里插入图片描述](https://www.icode9.com/i/ll/?i=2020112921425447.png?,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjI3MTYyNA==,size_16,color_FFFFFF,t_70