使用Dijkstra算法从加权图文本文件创建矩阵的最佳方法？

Question

我一直在研究图论和Dijsktra的，只是发现自己有太多的方法去做这件事，我不确定哪一个适用于这个具体的问题。以下是要求：

在集中式路由中，所有的路由信息都是在一个集中的位置生成和维护的。集中维护路由信息的常用方法是通过路由矩阵。路由矩阵对于网络中的每个节点都有一行和列，其中一行对应于源节点，列对应于目的节点。行i列j中的条目是一对(x，y)，其中x是从i到j的最短路径上的第一个节点，y是从i到j的最短路径的代价。

编写一个程序，读取表示网络的加权图，找到并输出相应的路由矩阵。路由矩阵将同时写入屏幕和输出文件。使用Dijkstra的算法寻找节点之间的最短代价和路径。该程序使用两个可选的命令行参数从命令行运行。使用以下命令行选项指示存在命令行参数：-i（用于输入文件名）和-o（用于输出文件名）。如果不存在命令行参数，程序将使用“xy_input.txt”和“xy_output.txt”分别作为默认输入和输出文件名。参见以下示例：

• Java xy_rmatrix
• Java xy_rmatrix-i xy_rmatrixi.txt-o xy-rmatrixo.txt

输入/输出示例：输入文件包含表示网络图形的零行或多行。每条线代表由两个顶点（路由器）和与它们之间的链路（通信线路）相关联的成本组成的双向边。一个或多个空白（空白、制表符等）将分隔每一行上的数据，节点名可能是一个字符串而不是一个字符。请注意，路由矩阵行和列是按字母顺序列出的。

输入：

输出：

我的主要问题是，对于这个特殊的问题，是否有必要将输入文件的内容存储在它自己的数据结构中，如图或邻接列表，以及我如何在Java中用顶点/节点和边来实现这些，使我能够执行Dijsktra的算法？

我假设指定的路由矩阵与邻接矩阵是同义词，这样做是否正确？

注意：我不是在钓代码，只是朝着正确的方向迈出了一步。

Answer 1

我认为在你的例子中，路由矩阵可以用二维数组来表示。Dijkstra的算法找到从一个源到任何目的地的最短路径。您可以先使用'A'作为源，然后使用'B'，依此类推，根据需要得到从每个点到每一个其他点的路由矩阵。您可以再次使用邻接列表或数组来表示图形信息，以便从每个源执行dijkstra。

希望这有帮助！