当前位置：首页 > news >正文

做网站网站建设专业公司哪家好百度下载免费官方安装

news 2026/4/12 23:53:03

做网站网站建设专业公司哪家好,百度下载免费官方安装,镇江疫情最新通知,延吉制作网站实验目的实现基于 Dijkstra 算法的路由软件实验内容网络拓扑如图所示实验过程先编写开辟应该图的空间，然后给点映射数字，构建图。程序获取用户输入的学号，构建图中边的权值。接下来程序从用户输入获取最短路径的搜索起点&#xff0…

实验目的

实现基于 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;}
}