#include<iostream>
#include<vector>
#define WQ 999 //表示无穷远
using namespace std;
int shortestPath_Dijkstra(vector<vector<int>> &v,int x,int y) { //x:从x节点出发 y:到y节点结束
if (x == y) return 0;
vector<int> visited(v.size()); //该节点是否访问过
vector<int> dist(v.size(),WQ); //记录最短距离
vector<int> path(v.size()); //记录该节点最短路径的前驱节点
//初始化三个数组
visited[x] = 1; dist[x] = 0; path[x] = 0;
for (int i=1; i < v.size(); i++) {
if (i == x) continue;
dist[i] = v[x][i];
path[i] = (v[x][i] == WQ ? 0 : x);
}
int next_node = x;
for (int j = 1; j < v.size() - 1; j++) {
int min_dist = WQ;
//寻找下一个要访问的节点
for (int i = 1; i < v.size(); i++) {
if (visited[i]) continue;
if (dist[i] < min_dist) {
min_dist = dist[i];
next_node = i;
}
}
visited[next_node] = 1;
//根据访问节点修改dist、path数组
for (int i = 1; i < v.size(); i++) {
if (visited[i] == 0 && dist[next_node] + v[next_node][i] < dist[i] && v[next_node][i]!=WQ) {
dist[i] = dist[next_node] + v[next_node][i];
path[i] = next_node;
}
}
}
return dist[y];
}
int main() {
int n, m,a,b,l,x,y;
while (cin >> n >> m) {
if (n > 10 || m > n * (n - 1) / 2) break;
vector<vector<int>> v_path(n+1, vector<int>(n+1, WQ));
while (m--) {
cin >> a >> b >> l;
v_path[a][b] = l;
v_path[b][a] = l;
}
for (int i = 1; i <= n; i++) v_path[i][i] = 0;
/*for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << v_path[i][j] << " ";
}cout << endl;
}
cout << v_path.size() << endl;*/
cin >> x >> y;
int r = shortestPath_Dijkstra(v_path, x, y);
if (r!=WQ) cout << r << endl;
else cout << "No path" << endl;
}
return 0;
}
数据结构与算法实验报告五(图的存储实现包括加权邻接矩阵,邻接表 图的遍历 最短路径-Dijkstra算法)
2024-07-16 20:32:01 20 阅读