最短路径（Dijsktra算法、Floyd算法）
1、最短路径：
两个结点之间，带权路径长度最短的路径。
常用算法是Dijkstra算法和Floyd算法，区别在于Dijsktra算法每次只能算出某一个结点到其他结点的最短路径，而Floyd算法可以直接把图中任意两个结点的最短路径都算出来。
最短路径一定是简单路径。
2、Dijkstra（迪杰斯特拉）算法
a、利用了三个数组
dist [ ] 表示距离源点的距离
path [ ] 记录现在结点的上一个结点
s [ ] 记录该结点有没有被访问过
b、无论用邻接矩阵还是邻接表存储，时间复杂度都为O（|V|2）
c、边上带有负权值时，不能使用Dijkstra算法。
d、每次都从中找未被访问过的距离源点最近哪个结点（比如离A最近的C），然后以这个结点（C）为中心，看这个结点（C）指向哪些其他的结点（E、F），然后更新这些结点（E、F）的值（就是如果加起来的值比原来的要小，则更新，说明找到更短的路径）。然后再从未访问的结点中，选取离源点最近的值，重复以上操作。等到所有结点都访问过后，最后一轮得到的就是所有其他结点到源点的最短路径长度。
e、答题的时候，一般要求把最后一轮得到的表写下来，根据这个表可以得到源点到其他结点最短路径长度，以及中间经过哪些结点。下图为一个例子：
3、Floyd（弗洛依德）算法
a、Floyd算法可以允许图中带有负权值的边，但是不能有带负权值的边组成的回路。
b、时间复杂度是O（|V|3），因为把建立临界矩阵需要遍历一遍，再一次轮流把经过每一个结点（第二遍），到达其他所有的结点（第三遍）的距离与现在的距离比较，如果更小则更新。
c、原理：
d、最终得到的表如何看最短路径和路径上经过的序列是多少：
下图为例子：比如a15，就是从1结点到5结点最短距离是60，从P矩阵可以知道，经过了4结点，即1 — 4 — 5，再看1，4之间，没有其他结点，4，5之间，又经过3结点。这样依次找下去，就可以得到路径。