迪杰特斯拉算法（Dijkstra‘s） - IT评测·应用市场-qidao123.com

#include<bits/stdc++.h>
using namespace std;
int n, m;//n为顶点数，m为边数
int matrix[100][100];//邻接矩阵
//初始化邻接矩阵
void init() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
matrix[i][j] = 0;
} else {
matrix[i][j] = INT_MAX;
}
}
}
}
//初始化beginPoint到其他点的距离
vector<int> initBeginDistance(int beginPoint) {
vector<int> beginDistance;
for (int i = 0; i < n; i++) {
beginDistance.push_back(matrix[beginPoint][i]);
}
return beginDistance;
}
//更新beginPoint到其他点的距离
void updateMatrix(int beginPoint, vector<int> distances) {
for (int i = 0; i < n; i++) {
matrix[beginPoint][i] = distances[i];
}
}
//打印邻接矩阵
void printMatrix() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << matrix[i][j] << " ";
}
cout << endl;
}
}
int main() {
cin >> n >> m;
init();//初始化邻接矩阵
for (int i = 0; i < m; i++) {
int x, y, dist;//x为起点，y为终点，distance为距离
cin >> x >> y >> dist;
matrix[x][y] = dist;
}
vector<int> already, unalready;//already为已经确定最短路径的点，unalready为未确定最短路径的点
for(int beginPoint = 0; beginPoint < n; beginPoint++) {
for(int i = 0; i < n; i++) {
if(i != beginPoint) {
unalready.push_back(i);
} else {
already.push_back(i);
}
}
//初始化beginPoint到其他点的距离
vector<int> distances = initBeginDistance(beginPoint);
while(unalready.size() > 0) {
int minDistance = INT_MAX, minIndex = -1;
//通过already中的点来更新beginPoint到unalready中的点的距离
for(int j = 0; j < unalready.size(); j++) {
if(distances[unalready[j]] <= minDistance) {
minDistance = distances[unalready[j]];
minIndex = unalready[j];
}
}
//将距离最小的点加入到already中，并从unalready中删除,并且跟新beginPoint到其他点的距离
already.push_back(minIndex);
unalready.erase(remove(unalready.begin(), unalready.end(), minIndex), unalready.end());
// 遍历未访问的节点
for(int j = 0; j < unalready.size(); j++) {
// 如果当前节点可以到未访问节点，并且未访问节点的距离大于当前节点到未访问节点的距离加上当前节点的距离
if(matrix[minIndex][unalready[j]] != INT_MAX && distances[unalready[j]] > distances[minIndex] + matrix[minIndex][unalready[j]]) {
// 更新未访问节点的距离
distances[unalready[j]] = distances[minIndex] + matrix[minIndex][unalready[j]];
}
}
}
updateMatrix(beginPoint, distances);
}
printMatrix();
return 0;
}
//输入：
// 5 11
// 0 1 8
// 0 2 32
// 1 0 12
// 1 2 16
// 1 3 15
// 2 1 29
// 2 4 13
// 3 1 21
// 3 4 7
// 4 2 27
// 4 3 19

复制代码