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

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

#include
#include
using namespace std;
vectorA;
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) {
}
else
{
}
}
}
for (int k = 1; k <= edgeNum; k++) {
int p1, p2,weight;
cout << "请输入第" << k << "条边的两个顶点以及权重：";
cin >> p1 >> p2 >> 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++) {
}
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]) {
}
}
}
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);
}

#include
#include
using namespace std;
vectorA;
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) {
}
else
{
}
}
}
for (int k = 1; k <= edgeNum; k++) {
int p1, p2,weight;
cout << "请输入第" << k << "条边的两个顶点以及权重：";
cin >> p1 >> p2 >> 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++) {
}
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]) {
}
}
}
}
void main() {
int nodeNum, edgeNum;
cout << "请输入图顶点个数=";
cin >> nodeNum;
cout << "请输入图边数=";
cin >> edgeNum;
createGraph(nodeNum,edgeNum);
//primAlgorithm(nodeNum);
dijkstraAlgorithm(nodeNum);
}