首页 » C++ » 普里姆算法和迪杰斯特拉算法

普里姆算法和迪杰斯特拉算法

原文 http://blog.csdn.net/syyyy712/article/details/79180455

2018-01-28 02:00:40阅读(481)

普里姆算法

普里姆算法不仅通过图构造生成树解决n个顶点之间的连通问题,同时使得总的耗费最小即最小代价生成树。
首先简单讲解一下普里姆算法的思想,如下图:
普里姆算法和迪杰<a href=斯特拉算法" src="http://img.blog.csdn.net/20180127133729318?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvc3l5eXk3MTI=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast" alt="这里写图片描述" title="">

首先第一张图为无向图,我们定义顶点1为初始点并且建立两个集合U和W,观察顶点1到其他顶点的距离,其中最短的是顶点3,因此将顶点1与顶点3之间连为实线,集合U中放入顶点3,W集中剩下2,4,5,6四个数;
第二步观察U集中顶点1和顶点3分别到W集中各个顶点的距离,如U集中的顶点1到W集中的顶点2距离是6,但是U集中的顶点3到W集中的顶点2距离是5,5<6,因此留下顶点3和顶点2的虚线,以此类推,得到了第二张图;
再次进行第一步找出权值最小的虚线画成实线,再次进行第二步,直到每一个顶点都被访问完结束。

以下是c++的普里姆算法的代码:

#include<iostream>
#include<vector>
using namespace std;
vector<int>A;
int adjMatrix[100][100];
int visited[100];
int init = 1000;
//用邻接矩阵存储图
void createGraph(int nodeNum,int edgeNum) {
    //初始化邻接矩阵
    for (int i = 1; i <= nodeNum; i++) {
        for (int j = 1; j <= nodeNum; j++) {
            if (i == j) {
                adjMatrix[i][j] = 0;
            }
            else
            {
                adjMatrix[i][j] = init;
            }
        }
    }
    for (int k = 1; k <= edgeNum; k++) {
        int p1, p2,weight;
        cout << "请输入第" << k << "条边的两个顶点以及权重:";
        cin >> p1 >> p2 >> weight;
        adjMatrix[p1][p2] = weight;
        adjMatrix[p2][p1] = weight;
    }
    cout << "图邻接矩阵:" << endl;
    for (int i = 1; i <= nodeNum; i++) {
        for (int j = 1; j <= nodeNum; j++) {
            cout << adjMatrix[i][j] << " ";
        }
        cout << endl;
    }
}
//普里姆算法
void primAlgorithm(int nodeNum) {
    int dis[100];
    //初始化第一行dis矩阵
    for (int i = 1; i <= nodeNum; i++) {
        dis[i] = adjMatrix[1][i];
    }
    visited[1] = 1;
    int count = 1;
    int sum = 0; 
    A.push_back(1);
    int j;
    while (count < nodeNum) {
        int min = init;
        //寻找最小权值顶点
        for (int i = 1; i <= nodeNum; i++) {
            if (visited[i] == 0 && dis[i] < min) {
                min = dis[i];
                j = i;
            }
        }
        visited[j] = 1;
        count++;
        sum = sum + dis[j];
        A.push_back(j);
        //更新dis矩阵
        for (int i = 1; i <= nodeNum; i++) {
            if (visited[i] == 0 && dis[i] > adjMatrix[j][i]) {
                dis[i] = adjMatrix[j][i];
            }
        }
    }
    cout << "集合U中的顶点存放顺序:";
    for (int i = 0; i < A.size()-1; i++) {
        cout << A[i] << "->";
    }
    cout << A[A.size() - 1];
    cout << endl;
    cout <<"最小权重和="<< sum << endl;
}
void main() {
    int nodeNum, edgeNum;
    cout << "请输入图顶点个数=";
    cin >> nodeNum;
    cout << "请输入图边数=";
    cin >> edgeNum;
    createGraph(nodeNum,edgeNum);
    primAlgorithm(nodeNum);
}

程序运行结果:
普里姆算法和迪杰斯特拉算法

迪杰斯特拉算法:

迪杰斯特拉算法解决的是单源最短路径,给定一个带权有向图D与源点v,求从v到D中其他顶点的最短路径。
具体做法:
设集合S存放一级钢求出的最短路径的终点,初始状态时,集合S中只有一个源点,设为v0,以后求得一条(v0,…….vk),就将vk加入到集合S中,直到全部的顶点都加入到集合S中,算法结束。为了当前找到的从源点v0到其他终点vi的最短路径长度,引入了一个dis[i]矩阵,该矩阵的每一个值表示从源点v0到终点vi的最短路径的长度。如下图所示:
普里姆算法和迪杰斯特拉算法

首先第一步将初始源点设为顶点1,因此问题就是顶点1到各个其他顶点的距离最短,从第一张有向图中可以得到最短的顶点1和顶点2,因此将顶点1和顶点2放入集合S中;
第二步找源点1到终点3的距离,顶点1到顶点3的距离是无穷大,但是如果经过顶点2到达顶点3则距离是3+25=28,但是如果经过顶点4再到达顶点3则距离是3+8+4=15,因此迪杰斯特拉选择先经过顶点4再到达顶点3,因此在S集中放入4,再放入3,最短距离是15;
第三步找源点1到终点5的距离,直接顶点1到顶点5的距离是30,如果经过顶点3再到顶点5的距离是3+8+4+10=25,如果是经过4到达5则距离为3+8+12=23,因此选择最后一条线路;

以下是c++的迪杰斯特拉算法的代码:

#include<iostream>
#include<vector>
using namespace std;
vector<int>A;
int adjMatrix[100][100];
int visited[100];
int init = 1000;
//用邻接矩阵存储图
void createGraph(int nodeNum,int edgeNum) {
    //初始化邻接矩阵
    for (int i = 1; i <= nodeNum; i++) {
        for (int j = 1; j <= nodeNum; j++) {
            if (i == j) {
                adjMatrix[i][j] = 0;
            }
            else
            {
                adjMatrix[i][j] = init;
            }
        }
    }
    for (int k = 1; k <= edgeNum; k++) {
        int p1, p2,weight;
        cout << "请输入第" << k << "条边的两个顶点以及权重:";
        cin >> p1 >> p2 >> weight;
        adjMatrix[p1][p2] = weight;
        //adjMatrix[p2][p1] = weight;
    }
    cout << "图邻接矩阵:" << endl;
    for (int i = 1; i <= nodeNum; i++) {
        for (int j = 1; j <= nodeNum; j++) {
            cout << adjMatrix[i][j] << " ";
        }
        cout << endl;
    }
}
//迪杰斯特拉
void dijkstraAlgorithm(int nodeNum) {
    int dis[100];
    //初始化第一行dis矩阵
    for (int i = 1; i <= nodeNum; i++) {
        dis[i] = adjMatrix[1][i];
    }
    visited[1] = 1;
    int count = 1;
    int sum = 0;
    int j;
    while (count < nodeNum) {
        int min = init;
        for (int i = 1; i <= nodeNum; i++) {
            if (visited[i] == 0 && dis[i] < min) {
                min = dis[i];
                j = i;
            }
        }
        visited[j] = 1;
        count++;
        //sum = sum + dis[j];
        sum = dis[j];
        cout << "从顶点1" << "->"<<"顶点"<< j << "最短路劲长度=" << sum << endl;
        for (int i = 1; i <= nodeNum; i++) {
            if (visited[i] == 0 && dis[i] > adjMatrix[j][i]+dis[j]) {
                dis[i] = adjMatrix[j][i]+dis[j];
            }
        }
    }
}
void main() {
    int nodeNum, edgeNum;
    cout << "请输入图顶点个数=";
    cin >> nodeNum;
    cout << "请输入图边数=";
    cin >> edgeNum;
    createGraph(nodeNum,edgeNum);
    //primAlgorithm(nodeNum);
    dijkstraAlgorithm(nodeNum);
}

程序运行结果:
普里姆算法和迪杰斯特拉算法

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹