最短路径（Shortest Path）
最短路径是指两个顶点之间权值之和最小的路径（有向图，无向图均可，不能有负权环）
最短路径到底表达的是什么意思呢？
例如下面的有向图
从顶点A出发，到达其余顶点的权值如下
如果是无向图
从顶点A出发，到达其余顶点的权值如下
如果是无权图，则相当于是全部边的权值为1的有权图
无权图同样有最短路径的概念，在这种情况下， 由于每条边的权值均相等，所以两个顶点之间，经过的边数量最少，就是两个顶点的最短路径。
无权有向图依然适用这种方法。
负权边
当有负权边，但是没有负权环时，依然存在最短路径。例如下面的有向图
其中
- A到E的最短路径是：A→B→E
负权环
有负权环时，不存在最短路径
例如下面的无向与有向图
例如
- 在有向图中，顶点D，E，F构成了环，并且成环中有边的权值为负数，这种环就称为负权环。
- 在无向图中，顶点D，E，F同样构成了环，并且成环中有边的权值为负数，这种环依然称为负权环。
为什么有负权环就没有最短路径呢？
假设现在要计算A到E的最短路径，现在的最短路径并不是A到E，而是A→E→D→F→E，这种情况下的权重是最小的，这时的权值是-1，如果继续以环进行绕圈，路径为A→E→D→F→E→D→F→E，现在的权值是-8。如果一直循环，最终得到的权值会越来越小。所以这种情况，A到E的路径可以无限段，所以不存在最短路径。
应用场景
最短路径的经典应用场景之一：路径规划问题
求最短路径的3个经典算法：
- 单源最短路径算法（单源：单个起点的意思；即从一个点出发，到其他点的最短路径）
- Dijkstra（迪杰斯特拉算法）
- Bellman-Ford（贝尔曼-福特算法）
- 多源最短路径算法（多源：多个起点；即从多个起点出发，到其他点的最短路径，能把这些顶点之间，互相到达的最短路径都计算出来）
- Floyd（弗洛伊德算法）
以上三种算法，都会在后面的内容中介绍到
完！
