Prim算法与Dijstra算法

注：参考如下文章和视频

不能说毫不相干，简直是一模一样(Prim vs Dijkstra)

普里姆和迪杰斯特拉太像了，他们有什么区别？

Prim算法和Dijkstra算法区别

总结

Prim算法解决连通无向有权图中最小生成树问题，而Dijkstra算法解决是源点到其余节点的最短路径问题。

两个算法在添加新结点时，都是选择“距离最短”的结点加入集合，但是Prim算法中，“距离最短”是指未访问的结点到已经访问的所有结点的一个集合的距离最小，将距离最小的结点加入到已访问的集合中；而在Dijkstra算法中，“距离最短”是指所有未访问结点到源点距离最小。

注：集合理解为将所有已访问的结点看成一个结点。

在Prim算法中，数组元素dist[i]表示未访问结点i到已访问结点集合的最短距离。而Dijkstra算法中，数组元素dist[i]表示未访问结点i到源点的最短距离。

数组元素的更新

//Prim算法
for(int i = 0; i < n; i++){   //G表示连通无向有权图，u表示新加入的结点。if(!vist[i] && G[u][i] < dist[i]){dist[i] = G[u][i];}
}//Dijkstra算法
for(int i = 0; i < n; i++){//注意两者在更新最短距离的区别，可以说这是两者唯一的区别if(!vist[i] && G[u][i] + dist[u] < dist[i]){dist[i] = G[u][i] + dist[u];}
}

两种算法的完整代码

void Prim(){fill(vis, 0, maxn);int len = 0;dist[0] = 0;for(int i = 1; i < n; i++){  //初始化数组dis[]dist[i] = G[0][i];}for(int i = 0; i < n; i++){int u = -1, min = INF;for(int j = 0; j < n; j++){if(!vist[j] && dist[j] < min){u = j;min = dist[j];}}if(u == -1) return ;len += min; vist[u] = 1;for(int v = 0; v < n; v++){if(!vist[v] && G[u][v] < dist[v])dist[v] = G[u][v];}}
}

void Dijkstra(){fill(vis, 0, maxn);fill(dis, dis + maxn, inf);dis[0] = 0; //将0设置为源点，同理可设置目标点，只需添加一个if判断即可for(int i = 0; i < n; i++){int u = -1, min = INF;for(int j = 0; j < n; j++){if(!vist[j] && dist[j] < min){u = j;min = dist[j];}}if(u == -1) return ;vis[u] = 1;for(int v = 0; v < n; v++){if(!vist[v] && G[u][v] + dist[u] < dist[v])dist[v] = G[u][v] + dist[u];}}
}

普里姆算法

算法步骤

1）首先将初始顶点u加入$U$中，对其与的每一个顶点$v_j$，将closedge[j]均初始化为到u的信息。

2）循环n-1次，做如下处理

• 从各组边closedge中选出最小的边closedgeK[k]，输出此边；
• 将k加入$U$中；
• 更新剩余的每组最小边信息closedge[j]，对于$V-U$中的边，新增了加了一条从k到j的边，如果新边的权值比closedge[j].lowcost更新为新的边的权值。

算法描述

//辅助数组的定义，用来记录从顶顶点集U到V-U的权值最小的边
struct
{VerTexType adjvex;//最小边在U中的那个顶点ArcType lowcost;//最小边上的权值
}closedge[MVNum];void MiniSpanTree_Prim(AMGraph G,VerTexType U)
{//无向网G以邻接矩阵形式存储，从顶点u出发构造G的最小生成树T，输出T的各条边k=LocateVex(G,u);//k为顶点u的下标for(j=0;j<G.vexnum;++j)//对v-U的每一个顶点初始化closedge[j]if(j!=k) closedge[j]={u,G.arcs[k] [j])};//{adjvex,lowcost)closedge[k].lowcost=0;//初始，U={u}for(i=1;i<G.vexnum;++i){//选择其余n-1个顶点，生成n-1条边（n=G.vexnum）k=Min(closedge);//求出T的下一个节点：第k个顶点，closedge[k]中存有当前最小边u0=closedge[k].adjvex;//u0为最小边的一个顶点，u0∈Uv0=G.vexs[k];//v0为最小边的另一个顶点，v0∈V-Ucout<<u0<<v0;//输出当前的最小边（u0，v0）closedge[k].lowcost=0;//第k个顶点并人U集for（j=0;j<G.vexnum;++j)if(G.arcs[k][j]<closedge[j].lowcost)//新顶点并人U后重新选择最小边closedge[j]={G.vexs[k],G.arcs[k] [j]];//for}
}

迪杰斯特拉算法

算法步骤

算法描述

补档

Prim算法的C语言实现

#include <stdio.h>
#include <limits.h>#define MAX_V 100
#define INF INT_MAXint graph[MAX_V][MAX_V]; // 邻接矩阵
int key[MAX_V];          // 存储最小边权
int parent[MAX_V];      // 存储生成树中的边
int inMST[MAX_V];       // 标记顶点是否在最小生成树中void prim(int start, int n) {for (int i = 0; i < n; i++) {key[i] = INF;    // 初始化为无穷大inMST[i] = 0;    // 初始化为不在生成树中parent[i] = -1;  // 初始化父节点}key[start] = 0;      // 起始顶点的键值为0for (int count = 0; count < n - 1; count++) {// 查找键值最小的顶点int u = -1;for (int v = 0; v < n; v++) {if (!inMST[v] && (u == -1 || key[v] < key[u])) {u = v;}}inMST[u] = 1; // 将该顶点加入最小生成树// 更新邻居的键值for (int v = 0; v < n; v++) {if (graph[u][v] && !inMST[v] && graph[u][v] < key[v]) {//注意两者区别parent[v] = u;key[v] = graph[u][v];}}}// 打印最小生成树for (int i = 1; i < n; i++) {printf("Edge: %d - %d, Weight: %d\n", parent[i], i, graph[parent[i]][i]);}
}

Dijkstra算法的C语言实现

#include <stdio.h>
#include <limits.h>#define MAX_V 100
#define INF INT_MAXint graph[MAX_V][MAX_V]; // 邻接矩阵
int key[MAX_V];          // 存储最短路径权重
int previous[MAX_V];     // 存储前驱节点
int inSPT[MAX_V];        // 标记顶点是否在最短路径树中void dijkstra(int start, int n) {for (int i = 0; i < n; i++) {key[i] = INF;        // 初始化为无穷大inSPT[i] = 0;        // 初始化为不在最短路径树中previous[i] = -1;    // 初始化前驱节点}key[start] = 0;          // 起始顶点的键值为0for (int count = 0; count < n - 1; count++) {// 查找键值最小的顶点int u = -1;for (int v = 0; v < n; v++) {if (!inSPT[v] && (u == -1 || key[v] < key[u])) {u = v;}}inSPT[u] = 1; // 将该顶点加入最短路径树// 更新邻居的键值for (int v = 0; v < n; v++) {if (graph[u][v] && !inSPT[v] && key[u] + graph[u][v] < key[v]) {//注意两者区别key[v] = key[u] + graph[u][v];previous[v] = u;}}}// 打印最短路径for (int i = 0; i < n; i++) {printf("Distance from %d to %d is %d\n", start, i, key[i]);}
}