有了加权有向图之后，我们立刻就能联想到实际生活中的使用场景，例如在一副地图中，找到顶点a与地点b之间的路径，这条路径可以是距离最短，也可以是时间最短，也可以是费用最小等，如果我们把 距离/时间/费用 看做是成本，那么就需要找到地点a和地点b之间成本最小的路径，也就是我们接下来要解决的最短路径问题。

一、最短路径定义及性质

定义：

在一副加权有向图中，从顶点s到顶点t的最短路径是所有从顶点s到顶点t的路径中总权重最小的那条路径。

性质：

1.路径具有方向性；

2.权重不一定等价于距离。权重可以是距离、时间、花费等内容，权重最小指的是成本最低

3.只考虑连通图。一副图中并不是所有的顶点都是可达的，如果s和t不可达，那么它们之间也就不存在最短路径， 为了简化问题，这里只考虑连通图。

4.最短路径不一定是唯一的。从一个顶点到达另外一个顶点的权重最小的路径可能会有很多条，这里只需要找出一 条即可。

最短路径树：

给定一副加权有向图和一个顶点s，以s为起点的一棵最短路径树是图的一副子图，它包含顶点s以及从s可达的所有 顶点。这棵有向树的根结点为s，树的每条路径都是有向图中的一条最短路径。

二、最短路径树API设计

计算最短路径树的经典算法是dijstra算法，为了实现它，先设计如下API：

三、松弛技术

松弛这个词来源于生活：一条橡皮筋沿着两个顶点的某条路径紧紧展开，如果这两个顶点之间的路径不止一条，还 有存在更短的路径，那么把皮筋转移到更短的路径上，皮筋就可以放松了。

松弛这种简单的原理刚好可以用来计算最短路径树。

在我们的API中，需要用到两个成员变量edgeTo和distTo，分别存储边和权重。一开始给定一幅图G和顶点s，我们只知道图的边以及这些边的权重，其他的一无所知，此时初始化顶点s到顶点s的最短路径的总权重disto[s]=0；顶点s到其他顶点的总权重默认为无穷大，随着算法的执行，不断的使用松弛技术处理图的边和顶点，并按一定的条件更新edgeTo和distTo中的数据，最终就可以得到最短路劲树。

边的松弛：

放松边v->w意味着检查从s到w的最短路径是否先从s到v，然后再从v到w？如果是，则v-w这条边需要加入到最短路径树中，更新edgeTo和distTo中的内容：edgeTo[w]=表示v->w这条边的DirectedEdge对象，distTo[w]=distTo[v]+v->w这条边的权重；

如果不是，则忽略v->w这条边。

顶点的松弛：

顶点的松弛是基于边的松弛完成的，只需要把某个顶点指出的所有边松弛，那么该顶点就松弛完毕。例如要松弛顶 点v，只需要遍历v的邻接表，把每一条边都松弛，那么顶点v就松弛了。

如果把起点设置为顶点0，那么找出起点0到顶点6的最短路径0->2->7>3->6的过程如下:

四、Dijstra算法实现

Disjstra算法的实现和Prim算法很类似，构造最短路径树的每一步都是向这棵树中添加一条新的边，而这条新的边 是有效横切边pq队列中的权重最小的边。（代码略，如需完整资料，请私信UP主）

本文未完，本文是Java数据结构与算法教程的课件文档，如需最新全套java数据结构算法，左神算法大厂LeetCode刷题教程请点击即可获取。