计算机网络——Dijkstra路由算法

devtools/2024/9/22 15:38:33/

实验目的

实现基于 Dijkstra 算法的路由软件

实验内容

网络拓扑如图所示

实验过程

先编写开辟应该图的空间，然后给点映射数字，构建图。程序获取用户输入的学号，构建图中边的权值。接下来程序从用户输入获取最短路径的搜索起点，然后运用dijkstra算法，计算最短路径然后输出，同时还会输出经过的点

关键代码

建图部分，先申请出这个图占用的空间，然后构建一个点到数字的映射，接着编写建图的函数划分学号中的数字来建图

std::vector<std::vector<int>> adj = {
//   u, v, w, x, y, z {0, 0, 0, 0, 0, 0},// u{0, 0, 0, 0, 0, 0},// v{0, 0, 0, 0, 0, 0},// w{0, 0, 0, 0, 0, 0},// x{0, 0, 0, 0, 0, 0},// y{0, 0, 0, 0, 0, 0} // z
};std::unordered_map<char, int> toint = {{'u', 0}, {'v', 1}, {'w', 2}, {'x', 3}, {'y', 4}, {'z', 5}
};
std::unordered_map<int, char> tochar = {{0, 'u'}, {1, 'v'}, {2, 'w'}, {3, 'x'}, {4, 'y'}, {5, 'z'}
};void addlink(char num, char a, char b) {int add;if (num == '0') {add = 10;}else {add = (int)(num - '0');}adj[toint[a]][toint[b]] = add;adj[toint[b]][toint[a]] = add;
}

算法部分，编写dijkstra算法来查找最短路径，这里用到了优先队列的思想，同时还额外构建了两个相关，一个用于实时更新最短距离，一个用于存储经过的点

void dijkstra(int src, std::vector<int>& dist, std::vector<int>& prev) {int n = adj.size();dist.assign(n, INF);prev.assign(n, -1);dist[src] = 0;std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;pq.push({0, src});while (!pq.empty()) {int v = pq.top().second;pq.pop();for (int u = 0; u < n; u++) {if (adj[v][u] != 0) {int new_dist = dist[v] + adj[v][u];if (new_dist < dist[u]) {dist[u] = new_dist;prev[u] = v;pq.push({new_dist, u});}}}}
}void printpath(int v, const std::vector<int>& prev, int end) {if (v < 0) return;printpath(prev[v], prev, end);if (end != v) {std::cout << tochar[v] << "-";}else {std::cout << tochar[v];}
}void printdijikstra(int start) {std::vector<int> dist, prev;dijkstra(start, dist, prev);for (int i = 1; i < adj.size(); i++) {printpath(i, prev, i);std::cout << ": " << dist[i] << std::endl;}
}