一、最短路问题
求图的最短路问题，几乎是图论的必学内容，而且在算法分析与设计中也会涉及。很多书上内容，
实在没法看，我们的图论教材，更是编的非常糟糕，吐槽，为啥要用自己学校编的破教材，不过据说
下一届终于要换书了。
言归正传，开始说明最短路问题。
1.问题描述：
对一幅图G，我们对每一条边赋权w(e)，成为一个赋权图。H是G的一个子图，则W(H) = sigma(w(e)),
也就是对每条边的权求和。寻找从一个点a到另一个b的一个子图，使得权和最小，即为最短路问题。
2.算法描述：
Dijkstra(迪杰斯特拉算法算法)：
我表示看到后，是懵逼的，接下来详细分析下。
算法图解:
其实就是不断求一个点集合中的每个点，和与他相邻点最短路的最小值。我们还是从实例出发，更
容易讲解。我会把上述步骤，拆解为多步。
我们求下面这个图从A到L的最短路。
- 第一步：
令a1 = A(便于标记),t(a1) = 0(表示点a1到a的最短路)，S={a1}(被选择的点的集合)，T = 0
(空集 表示被选择的最短路的边集)。
- 第二步：
求与S中的点a1与他相邻的点的距离d，取点a2 = C使得距离最小。令S={a1,a2}，T={AC}。
- 第三步：
重复第二步，求S中的点a1,a2的相邻点中(去除已选择点)，距离最小的那个，则为AB，CE。
再取AB，CE中权和最小的一个，B，所以a3=B,令S={a1,a2,a3}，T={AC,AB}。 - ……
持续下去，不断寻找，S集合中的每个点与他相邻点的最小距离，然后再这些最小距离中找到最小的
那个加入到S中，同时加入相应的边。
直到到达终点L为止。最后得到的最短路为：
此算法是多项式时间可求解的，
关于算法的实现可以在参考资料中找到。
二、最小生成树
问题描述
同样在一个连通赋权图中，寻找一颗生成树使得权和最小。
此算法比较简单，很容易理解。
算法描述：
Kruskal算法：
不断寻找最小权的边即可。
比如，寻找下图的最小生成树。
结果如下
本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请
点击举报。
