网站程序基础,开发公司发言稿观摩会,商贸有限公司门头照片,中国工商建设标准化协会网站注#xff1a;参考如下文章和视频
不能说毫不相干#xff0c;简直是一模一样(Prim vs Dijkstra)
普里姆和迪杰斯特拉太像了#xff0c;他们有什么区别#xff1f;
Prim算法和Dijkstra算法区别 文章目录 总结数组元素的更新两种算法的完整代码 普里姆算法算法步骤算法描…注参考如下文章和视频
不能说毫不相干简直是一模一样(Prim vs Dijkstra)
普里姆和迪杰斯特拉太像了他们有什么区别
Prim算法和Dijkstra算法区别 文章目录 总结数组元素的更新两种算法的完整代码 普里姆算法算法步骤算法描述 迪杰斯特拉算法算法步骤算法描述 补档Prim算法的C语言实现Dijkstra算法的C语言实现 总结
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 U U中对其与的每一个顶点 v j v_j vj将closedge[j]均初始化为到u的信息。
2循环n-1次做如下处理
从各组边closedge中选出最小的边closedgeK[k]输出此边将k加入 U U U中更新剩余的每组最小边信息closedge[j]对于 V − U V-U 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的各条边kLocateVex(G,u);//k为顶点u的下标for(j0;jG.vexnum;j)//对v-U的每一个顶点初始化closedge[j]if(j!k) closedge[j]{u,G.arcs[k] [j])};//{adjvex,lowcost)closedge[k].lowcost0;//初始U{u}for(i1;iG.vexnum;i){//选择其余n-1个顶点生成n-1条边nG.vexnumkMin(closedge);//求出T的下一个节点第k个顶点closedge[k]中存有当前最小边u0closedge[k].adjvex;//u0为最小边的一个顶点u0∈Uv0G.vexs[k];//v0为最小边的另一个顶点v0∈V-Ucoutu0v0;//输出当前的最小边u0v0closedge[k].lowcost0;//第k个顶点并人U集forj0;jG.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]);}
}
