0

我目前正在做一项家庭作业，要求我：

使用二进制堆实现 DIJKSTRA 的单源最短路径问题算法。运行时间应为 O(ElogV)。

够简单！但是，问题必须通过代码来解决。在此之前仍然不是那么困难的概念：

您的程序应该从文件中读取数据（参见下面的示例）并输出一个数字 = 从节点 0 到每个节点的最短路径的长度之和。输入格式：下面每个文件的第一行包含图中的顶点数和边数（格式为“n=XXXX m=XXXXX”）。文件的其余部分组织如下：每个顶点 i 单独出现在一行上，然后是 i 的每个邻居 j>i 的一行（包含 j 和边的长度 (i,j)）。每个邻居列表都以空行结束。不表示没有索引大于 i 的邻居的顶点 i。注意：顶点的索引从 0 到 n-1。注意：每条边仅被提及一次，其端点数量较小，SAMPLE INPUT: 1. first input 2.第二个输入 最短路径树的长度应该分别是10721073和625349。程序应在 3-10 秒内为第一个输入提供输出，第二个输入应在 1 秒内输出。

我的问题：我不太明白我的教授对文件格式的解释以及它们应该如何翻译成代码。我也不明白我应该可视化什么样的图，我是在二叉树上找到最短路径，还是在具有许多顶点和边的图（不是二叉树）上找到最短路径？（我很困惑，因为他提到了二进制堆，所以我不确定在这里可视化什么）

我不明白的文件怎么办：看看图表，我们有这样的东西：

n=25000 m=576014
0
   176     67
   665    185
  1129     26
  1414    114
  1748    205
  2027    264
  2714    212
  2743    132 ...

从他的解释中，我明白n = number of vertices了m = number of edges。我不明白的是，在0我应该使用 Dijkstra 的图形中，顶点后的数字对代表什么。此外，如果您查看任一文件的末尾，您会注意到以这种格式列出的顶点数不是n ='s. 为什么是这样？

4

0 回答 0