透彻_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。

数组，记录了所有确定点通往未确定点的代价。下标是和下标同步的终点！也就是当前是未确定点的顶点里的内容，记录这进入这个顶点的最小代价。每次把代价最小的点拿出来，确定这个点！

代码有三部分，第零部分是初始化，第一部分是【大循环里的子循环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的其实有体现。

2.Path[i]：记录源点到i点当前最短路径上i点的直接前驱顶点序号，相当于Prim的数组。【路是一步步走的，记它的上一步就好，上一步还记得上上步。】

3.D[i]：记录源点到i点的当前最短路径长度，相当于Prim的数组。

代码

#pragma region Dijkstra
typedef int Patharc[MAXVEX];    /* 用于存储最短路径下标的数组 */
typedef int ShortPathTable[MAXVEX];/* 用于存储到各点最短路径的权值和 */
/*  Dijkstra算法，求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度D[v] */
/*  P[v]的值为前驱顶点下标,D[v]表示v0到v的最短路径长度和 */
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc &P, ShortPathTable &D) {int v, w, k, min;int final[MAXVEX];/* final[w]=1表示求得顶点v0至vw的最短路径 */for (v = 0; v < G.numVertexes; v++)    /* 初始化数据 */{final[v] = 0;			/* 全部顶点初始化为未知最短路径状态 */D[v] = G.arc[v0][v];/* 将与v0点有连线的顶点加上权值 */P[v] = -1;				/* 初始化路径数组P为-1  */}D[v0] = 0;  /* v0至v0路径为0 */final[v0] = 1;    /* v0至v0不需要求路径 *//* 开始主循环，每次求得v0到某个v顶点的最短路径 */for (v = 1; v < G.numVertexes; v++) {min = INFINITY;    /* 当前所知离v0顶点的最近距离 */for (w = 0; w < G.numVertexes; w++) /* 寻找离v0最近的顶点 */{if (!final[w] && D[w] < min) {k = w;min = D[w];    /* w顶点离v0顶点更近 */}}final[k] = 1;    /* 将目前找到的最近的顶点置为1 */for (w = 0; w < G.numVertexes; w++) /* 修正当前最短路径及距离 */{/* 如果经过v顶点的路径比现在这条路径的长度短的话 */if (!final[w] && (min + G.arc[k][w] < D[w])) { /*  说明找到了更短的路径，修改D[w]和P[w] */D[w] = min + G.arc[k][w];  /* 修改当前路径长度 */P[w] = k;}}}
}
#pragma endregion

同样是三个部分。初始化+大循环内子循环1+大循环内子循环2

零：final[v] = 0; D[v] = G.arc[v0][v];P[v] = -1;

一：min = D[w]; k = w;

二：P[w] = k; D[w] = min + G.arc[k][w];

求单源点到其他点，时间复杂度O(n2)。如果求图中任意两点，每个点来一次，存起来。O(n3)

完整的求最短路径代码

from大话数据结构

#include "stdio.h"    
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0#define MAXEDGE 20
#define MAXVEX 20
#define INFINITY 65535typedef int Status;	/* Status是函数的类型,其值是函数结果状态代码，如OK等 */ typedef struct
{int vexs[MAXVEX];int arc[MAXVEX][MAXVEX];int numVertexes, numEdges;
}MGraph;typedef int Patharc[MAXVEX];    /* 用于存储最短路径下标的数组 */
typedef int ShortPathTable[MAXVEX];/* 用于存储到各点最短路径的权值和 *//* 构件图 */
void CreateMGraph(MGraph *G)
{int i, j;/* printf("请输入边数和顶点数:"); */G->numEdges=16;G->numVertexes=9;for (i = 0; i < G->numVertexes; i++)/* 初始化图 */{G->vexs[i]=i;}for (i = 0; i < G->numVertexes; i++)/* 初始化图 */{for ( j = 0; j < G->numVertexes; j++){if (i==j)G->arc[i][j]=0;elseG->arc[i][j] = G->arc[j][i] = INFINITY;}}G->arc[0][1]=1;G->arc[0][2]=5; G->arc[1][2]=3; G->arc[1][3]=7; G->arc[1][4]=5; G->arc[2][4]=1; G->arc[2][5]=7; G->arc[3][4]=2; G->arc[3][6]=3; G->arc[4][5]=3;G->arc[4][6]=6;G->arc[4][7]=9; G->arc[5][7]=5; G->arc[6][7]=2; G->arc[6][8]=7;G->arc[7][8]=4;for(i = 0; i < G->numVertexes; i++){for(j = i; j < G->numVertexes; j++){G->arc[j][i] =G->arc[i][j];}}}/*  Dijkstra算法，求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度D[v] */    
/*  P[v]的值为前驱顶点下标,D[v]表示v0到v的最短路径长度和 */  
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D)
{    int v,w,k,min;    int final[MAXVEX];/* final[w]=1表示求得顶点v0至vw的最短路径 */for(v=0; v<G.numVertexes; v++)    /* 初始化数据 */{        final[v] = 0;			/* 全部顶点初始化为未知最短路径状态 */(*D)[v] = G.arc[v0][v];/* 将与v0点有连线的顶点加上权值 */(*P)[v] = -1;				/* 初始化路径数组P为-1  */       }(*D)[v0] = 0;  /* v0至v0路径为0 */  final[v0] = 1;    /* v0至v0不需要求路径 */        /* 开始主循环，每次求得v0到某个v顶点的最短路径 */   for(v=1; v<G.numVertexes; v++)   {min=INFINITY;    /* 当前所知离v0顶点的最近距离 */        for(w=0; w<G.numVertexes; w++) /* 寻找离v0最近的顶点 */    {            if(!final[w] && (*D)[w]<min)             {                   k=w;                    min = (*D)[w];    /* w顶点离v0顶点更近 */            }        }        final[k] = 1;    /* 将目前找到的最近的顶点置为1 */for(w=0; w<G.numVertexes; w++) /* 修正当前最短路径及距离 */{/* 如果经过v顶点的路径比现在这条路径的长度短的话 */if(!final[w] && (min+G.arc[k][w]<(*D)[w]))   { /*  说明找到了更短的路径，修改D[w]和P[w] */(*D)[w] = min + G.arc[k][w];  /* 修改当前路径长度 */               (*P)[w]=k;        }       }   }
}int main(void)
{   int i,j,v0;MGraph G;    Patharc P;    ShortPathTable D; /* 求某点到其余各点的最短路径 */   v0=0;CreateMGraph(&G);ShortestPath_Dijkstra(G, v0, &P, &D);  printf("最短路径倒序如下:\n");    for(i=1;i<G.numVertexes;++i)   {       printf("v%d - v%d : ",v0,i);j=i;while(P[j]!=-1){printf("%d ",P[j]);j=P[j];}printf("\n");}    printf("\n源点到各顶点的最短路径长度为:\n");  for(i=1;i<G.numVertexes;++i)        printf("v%d - v%d : %d \n",G.vexs[0],G.vexs[i],D[i]);     return 0;
}

感觉算法优化空间很大，毕竟很多点不用重复遍历。

有空再学。