自学内容网 自学内容网
自学内容网 > 正文

Prim算法与Dijstra算法

🕗 发布于 2024-11-05 11:20 考研  学习  数据结构  

注：参考如下文章和视频

不能说毫不相干，简直是一模一样(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 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的各条边
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∈U
        v0=G.vexs[k];//v0为最小边的另一个顶点，v0∈V-U
        cout<<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_MAX

int 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;      // 起始顶点的键值为0

    for (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_MAX

int 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;          // 起始顶点的键值为0

    for (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]);
    }
}

原文地址：https://blog.csdn.net/m0_61049985/article/details/143473530

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024