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

数组，记录了所有确定点通往未确定点的代价。下标是和下标同步的终点！也就是当前是未确定点的顶点里的内容，记录这进入这个顶点的最小代价。每次把代价最小的点拿出来，确定这个点！
代码有三部分，第零部分是初始化，第一部分是【大循环里的子循环while】，第二部分是【大循环里的子循环for】
每次大循环都会确定一个点。
Prim代码
from大话数据结构
/* Prim算法生成最小生成树*/void MiniSpanTree_Prim(MGraph G) {int min, i, j, k;int adjvex[MAXVEX];/* 保存相关顶点下标 */int lowcost[MAXVEX]; /* 保存相关顶点间边的权值 */lowcost[0] = 0;/* 初始化第一个权值为0，即v0加入生成树 *//* lowcost的值为0，在这里就是此下标的顶点已经加入生成树 */adjvex[0] = 0;/* 初始化第一个顶点下标为0 */for (i = 1; i < G.numVertexes; i++) /* 循环除下标为0外的全部顶点 */{lowcost[i] = G.arc[0][i]; /* 将v0顶点与之有边的权值存入数组 */adjvex[i] = 0;/* 初始化都为v0的下标 */}for (i = 1; i < G.numVertexes; i++) {min = INFINITY; /* 初始化最小权值为∞，*//* 通常设置为不可能的大数字如32767、65535等 */j = 1; k = 0;while (j < G.numVertexes) /* 循环全部顶点 */{if (lowcost[j] != 0 && lowcost[j] < min)/* 如果权值不为0且权值小于min */{min = lowcost[j]; /* 则让当前权值成为最小值 */k = j;/* 将当前最小值的下标存入k */}j++;}printf("(%d, %d)\n", adjvex[k], k);/* 打印当前顶点边中权值最小的边 */lowcost[k] = 0;/* 将当前顶点的权值设置为0,表示此顶点已经完成任务 */for (j = 1; j < G.numVertexes; j++) /* 循环所有顶点 */{if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j]) {/* 如果下标为k顶点各边权值小于此前这些顶点未被加入生成树权值 */lowcost[j] = G.arc[k][j];/* 将较小的权值存入lowcost相应位置 */adjvex[j] = k;/* 将下标为k的顶点存入adjvex */}}}}
第零部分，实现“目前能前往的点有哪些？到这些点的代价是多少？” [i] = 0;[i] = G.arc[0][i];
【1、2，候选】
第一部分，实现“挑最短的” 。min = [j];k = j;
【1、2里选1为终点】
这一部分不需要考虑数组，不必知道起点是谁，只要知道到等会要到哪个终点，到这个终点的代价。
两个子循环中间，输出结果，并实现一个"确定k点"的操作。
第二部分，实现“目前能前往的点有哪些？到这些点的代价是多少？”[j] = k; [j] = G.arc[k][j];
【1选X、X、X，XXX会在下次的while循环里和刚才落选的2号点共同竞争】
第二部分和第零部分的区别是，0变成了k 。0和k有什么区别？0是静止的，初始化的循环里不变。k也是静止的，第三部分的循环里不变。
只看两个循环，其实没什么区别。
但k不是永远静止的。k每次会在第二部分代表最终确认的j，也就是连接着目前最小代价路线的，被挑到的终点。
k是挑出来的终点，但对于下面的j，k变成了起点。[j] = k之后，[j]即Vk会访问Vj 。这里，定义了谁会访问Vj，谁会把Vj当作终点。他们都会在下次一大循环里的while中竞争，胜利者变成k 。
那么下一次大循环时，第一部分从k点指向的点继续搜寻，产生一个新的k 。k就这样不断更新。
双层循环，时间复杂度O(n2) 。适合稠密图。
迪杰斯特拉算法
解决单源点的最短路径问题。
原理是：已确定源点到2号点的最短路径，那么2号到3号之间的最短路径可能就是源点到3号点的最短路径。同样，三号点的旁边的路线都看得见时，就能最终确定。
原理和代码结构上与Prim基本一致。
需要三个一维数组辅助。
1.S[i] ：记录源点到i点是否确定了最短路径。这在Prim的其实有体现。