ZBLOG

void Dijkstra(ALDirNetwork& graph, int v0, int* dist, int* path) { int mindist, infinity = graph.GetInfinity(); int v, u; for (v = 0; v < graph.GetVexNum(); v++) { dist[v] = graph.GetWeight(v0, v); if (dist[v] == infinity) path[v...

根据您提供的代码,我稍作修改实现了利用Dijkstra算法求指定源点到其余各顶点的最短路径,并输出最短路径及其长度。以下是修改后的代码:

  1. #include <iostream>
  2. #include "ALDirNetwork.h"
  3. #include "SqStack.h"
  4. void Dijkstra(ALDirNetwork<char, int>& graph, int v0, int* dist, int* path)
  5. {
  6. const int infinity = graph.GetInfinity();
  7. int vertexCount = graph.GetVexNum();
  8. for (int v = 0; v < vertexCount; ++v) {
  9. dist[v] = graph.GetWeight(v0, v);
  10. if (dist[v] == infinity) {
  11. path[v] = -1;
  12. } else {
  13. path[v] = v0;
  14. }
  15. }
  16. graph.SetVisitedTag(v0, VISITED);
  17. for (int i = 1; i < vertexCount; ++i) {
  18. int u = v0;
  19. int minDist = infinity;
  20. // Find the unvisited vertex with minimum distance
  21. for (int v = 0; v < vertexCount; ++v) {
  22. if (graph.GetVisitedTag(v) == UNVISITED && dist[v] < minDist) {
  23. u = v;
  24. minDist = dist[v];
  25. }
  26. }
  27. graph.SetVisitedTag(u, VISITED);
  28. // Update distances and paths for adjacent vertices
  29. for (int v = graph.GetFirstAdjvex(u); v != -1; v = graph.GetNextAdjvex(u, v)) {
  30. if (graph.GetVisitedTag(v) == UNVISITED && minDist + graph.GetWeight(u, v) < dist[v]) {
  31. dist[v] = minDist + graph.GetWeight(u, v);
  32. path[v] = u;
  33. }
  34. }
  35. }
  36. }
  37. void OutputShortestPath(ALDirNetwork<char, int>& graph, int v0, int* dist, int* path)
  38. {
  39. char vertex;
  40. graph.GetElem(v0, vertex);
  41. int vertexCount = graph.GetVexNum();
  42. for (int i = 0; i < vertexCount; ++i) {
  43. if (i != v0) {
  44. char destVertex;
  45. graph.GetElem(i, destVertex);
  46. if (dist[i] == graph.GetInfinity()) {
  47. std::cout << "There is no path between " << vertex << " and " << destVertex << "\n";
  48. continue;
  49. }
  50. std::cout << "The shortest path between " << vertex << " and " << destVertex << " is: ";
  51. // Output the vertices on the shortest path
  52. SqStack<int> stack;
  53. int index = i;
  54. while (path[index] != -1) {
  55. stack.Push(index);
  56. index = path[index];
  57. }
  58. std::cout << vertex;
  59. while (!stack.IsEmpty()) {
  60. char tmp;
  61. int k;
  62. stack.Pop(k);
  63. graph.GetElem(k, tmp);
  64. std::cout << " -> " << tmp;
  65. }
  66. std::cout << "\nThe distance is: " << dist[i] << "\n";
  67. }
  68. }
  69. }
  70. int main()
  71. {
  72. ALDirNetwork<char, int> graph(6); // 创建一个有6个顶点的邻接表表示的有向图
  73. // 添加边和权值
  74. graph.AddEdge(0, 1, 2);
  75. graph.AddEdge(0, 2, 4);
  76. graph.AddEdge(1, 2, 1);
  77. graph.AddEdge(1, 3, 4);
  78. graph.AddEdge(2, 3, 1);
  79. graph.AddEdge(2, 4, 3);
  80. graph.AddEdge(3, 4, 5);
  81. graph.AddEdge(3, 5, 6);
  82. graph.AddEdge(4, 5, 2);
  83. int* dist = new int[graph.GetVexNum()];
  84. int* path = new int[graph.GetVexNum()];
  85. // 指定源点为顶点0
  86. Dijkstra(graph, 0, dist, path);
  87. // 输出最短路径及其长度
  88. OutputShortestPath(graph, 0, dist, path);
  89. delete[] dist;
  90. delete[] path;
  91. return 0;
  92. }

请根据需要将该代码添加到您的程序中,并根据实际情况进行适当修改。


内容由零声教学AI助手提供,问题来源于学员提问

本站部分文章来源于网络,版权归原作者所有,如有侵权请联系站长删除。
转载请注明出处:https://golang.0voice.com/?id=9390

分享:
扫描分享到社交APP
上一篇
下一篇
发表列表
游客 游客
此处应有掌声~
评论列表

还没有评论,快来说点什么吧~

联系我们

在线咨询: 点击这里给我发消息

微信号:3007537140

上班时间: 10:30-22:30

关注我们
x

注册

已经有帐号?