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

2018-01-29 12:40:55来源:网络收集作者:管理员人点击

分享

普里姆算法:

普里姆算法不仅通过图构造生成树解决n个顶点之间的连通问题,同时使得总的耗费最小即最小代价生成树。
首先简单讲解一下普里姆算法的思想,如下图:
普里姆算法和迪杰斯特拉算法


首先第一张图为无向图,我们定义顶点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
#include
using namespace std;
vectorA;
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
#include
using namespace std;
vectorA;
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);
}

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


最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台