本文实例为大家分享了C++简单实现Dijkstra算法的具体代码，供大家参考，具体内容如下
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
// Dijkstra.cpp : 定义控制台应用程序的入口点。// #include "stdafx.h"#include <iostream>#include <stack>#define MAX_VALUE 1000using namespace std; struct MGraph{ int *edges[MAX_VALUE]; int iVertexCount, iEdageCount;};void ReadDate(MGraph *mGraph, int *iBegin, int *iEnd);void Dijkstra(MGraph *mGraph, int *pArrDis, int *pArrPath, int iBegin);void PrintResult(int *pArrDis, int *pArrPath, int iBegin, int iEnd); int main(){ int iBegin, iEnd; int *pArrPath = new int[MAX_VALUE]; int *pArrDis = new int[MAX_VALUE]; MGraph mGraph; for (int i = 0; i < MAX_VALUE; i++){ mGraph.edges[i] = new int[MAX_VALUE]; } ReadDate(&mGraph, &iBegin, &iEnd); Dijkstra(&mGraph, pArrDis, pArrPath, iBegin); PrintResult(pArrDis,pArrPath, iBegin, iEnd); system("pause"); return 0;} void ReadDate(MGraph *mGraph, int *iBegin, int *iEnd){ cout << "请输入顶点数量" << endl; cin >> mGraph->iVertexCount; cout << "请输入邻接矩阵数据：" << endl; for (int iRow = 1; iRow <= mGraph->iVertexCount; iRow++){ for (int iCol = 1; iCol <= mGraph->iVertexCount; iCol++){ cin >> mGraph->edges[iRow][iCol]; } } //cout << "请输入顶点数和边数" << endl; //cin >> mGraph->iVertexCount >> mGraph->iEdageCount; //for (int iRow = 1; iRow <= mGraph->iVertexCount; iRow++){ // for (int iCol = 1; iCol <= mGraph->iVertexCount; iCol++){ // mGraph->edges[iRow][iCol] = -1; // } //} //cout << "请输入连通边及权重" << endl; //int iRow, iCol, iWeight; //for (int i = 1; i <= mGraph->iEdageCount; i++){ // cin >> iRow >> iCol >> iWeight; // mGraph->edges[iRow][iCol] = iWeight; //} cout << "请输入查询的起点和终点" << endl; cin >> *iBegin >> *iEnd;} void Dijkstra(MGraph *mGraph, int *pArrDis, int *pArrPath, int iBegin){ int iMin; int bArrVisited[MAX_VALUE]; memset(bArrVisited, false, sizeof(bArrVisited)); for (int i = 1; i <= mGraph->iVertexCount; i++){ pArrPath[i] = -1; mGraph->edges[i][i] = 0; pArrDis[i] = mGraph->edges[iBegin][i] != -1 ? mGraph->edges[iBegin][i] : INT_MAX; } int iNewCost; int iSelected = iBegin; for (int i = 1; i <= mGraph->iVertexCount; i++){ int iPre = iSelected; iMin = INT_MAX; for (int j = 1; j <= mGraph->iVertexCount; j++){ if (!bArrVisited[j] && pArrDis[j] < iMin){ iMin = pArrDis[j]; iSelected = j; } } for (int j = 1; j <= mGraph->iVertexCount; j++){ iNewCost = pArrDis[iSelected] != -1 && mGraph->edges[iSelected][j] != -1 ? pArrDis[iSelected] + mGraph->edges[iSelected][j] : INT_MAX; if (!bArrVisited[j] && iNewCost < pArrDis[j]){ pArrPath[j] = iSelected; pArrDis[j] = iNewCost; //pArrPath[iSelected] = iSelected; } } //pArrPath[iSelected] = iPre; bArrVisited[iSelected] = true; }} void PrintResult(int *pArrDis, int *pArrPath, int iBegin, int iEnd){ cout << "从" << iBegin << "开始到" << iEnd << "的最短路径长度为"; cout << pArrDis[iEnd] << endl; cout << "所经过的最短路径节点为："; stack<int> stackVertices; int k = iEnd; do{ k = pArrPath[k]; stackVertices.push(k); } while (k != pArrPath[k] && k != -1); cout << stackVertices.top()*-1; stackVertices.pop(); unsigned int nLength = stackVertices.size(); for (unsigned int nIndex = 0; nIndex < nLength; nIndex++) { cout << " -> " << stackVertices.top(); stackVertices.pop(); } cout << " -> " << iEnd << endl;} |
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/u012102306/article/details/49871909
