透彻_Prim普里姆算法和Dijkstra迪杰斯特拉算法_最小生成树和最短路径 _循环

^ ^迪杰斯特拉算法
普里姆算法
最小生成树问题。
目的：访问所有点。所以只要知道对于每个点，从哪里访问它,消耗最少。
在最小生成树里，每个点只被访问一次，而这条访问边，一定是与这个点相连的边里消耗最小的边。
在这里，点有三种状态：
1.确定点，已经在结果里；
2.未确定点，和确定点相连，不能保证从现在的确定点出发代价最小，是看得见的点。
3.未知点。没有和任何确定点相连，还在黑暗迷雾中。
MST性质
MST性质的解释:有很多条边(ui,vi)，ui是确定点，vi是未确定点，那么如果其中的一条(u,v)的权值是数条(ui,vi)中最小的，那么这条边是可以作为结果的。v加入ui，完整确定。
也就是：目前能前往的点有哪些？到这些点的代价是多少？挑代价最小的走。
原理
“挑最短的走”，挑的是确定点和未确定点之间的最短路。但未知点里可能有去这个未确定点的更短的路。
现在选中的边，其实不一定是与这个点相连的边中的最小边，但最小边马上会被选中。
如果选中的不是最小边，在这个点从未确定点变成确定点之后，我们也就看得到，谁才是这个点周围的最小边。这个点也会从最小边去访问其他点。如这幅图。虽然S到B的路17，不是B周围的最短路，但一走到B，B点一确认，就看到新增确认点B与新增未确认点之间的路径，14是现在已知的最短路径，直接走。为什么是马上？比如有很多到其他未确定的，且比14小的，那不是要先走他们嘛？…那刚才也不走17啊！现在是假设走17，那么17在刚才是作为全局最短，才能走。现在来了个比17还短的，这波必不可能输啊。
那点周围的最小边有可能不被选中吗？不可能。只要是符合定义的最小生成树，就一定会选中每个点周围的最小边。
因为整个网，最终选中的生成树不能是环状！我们的结果是正确的最小生成树！那么我们就不会有环！
反证法：不合理情况：假设偏要不走14，还能保证是最小生成树吗？
假设我们走到了B点，把B确定了，但我们不去访问对岸的点的情况只有一种：对面A点已经是确定点了。因为是只有一个出发点，也就意味着：妈呀，他从另一边绕过来了！A要找最小生成树，根据最小生成树的定义，A要确定B点，要走14 。一走就坏了，呼应上了，成为了一个环，这是不行的。那咋办嘛？幸好只是假设走到B这个点，实际上这个数据只是暂时记录，还没确定呢！在这里14更小，那么B点就投向了A的怀抱！
也就是S点和A点对B的争夺中，A取胜了。也就是如果从另一边绕进来，甚至不会选中刚才的 “非最短的最小边”–S到B的17 。
反方向，从被访问点的角度看。任意一个点，看看它周围的边。最小的权值的边，一定被囊括在结果之中。
在下图里，任意一个点，与他连接的几条边中的最小边，一定被选中了。
然后着眼于最小边。选中这个点周围最小边的那一瞬间，我们先看做这个点是被访问的，是作为弧头/终点的。如图中，V3这个点，权值等于1的最小边，从V1进入V3，V3是终点。V3周围其他的边，都比1大，若是其他边被选中，我们看做V3是作为起点，把其他边当作终点。这样就如同开头所说的目的：”访问所有点。所以只要知道对于每个点，从哪里访问它消耗最少。”这一段都是歪理。
原理就是这样。
实现
“现在看得到的点有哪些？到这些点的代价是多少？挑最短的走。”
这里设存储结构是邻接矩阵。
需要两个一维数组。
数组，记录顶点之间的连接状况，V数组内容=起点，V数组下标=终点。也就是从里可以知道，[i]访问了Vi点。[i]→i 。