使用 Dijkstra 算法从加权图形文本文件创建矩阵的最佳方法？
Best way to create matrix from a weighted graph text file using Dijkstra's Algorithm?
我一直在研究图论和 Dijsktra，只是发现自己有太多方法可以解决这个问题，而且我不确定该用哪种方法来解决这个特定问题。以下是要求：
In centralized routing, all the routing information is generated and maintained in a centralized location. A common way of maintaining routing information centrally is via a routing matrix. A routing matrix has a row and a column for each node in the network, where a row corresponds to the source node and a column corresponds to the destination node. The entry in row i column j is a pair (x , y), where x is the first node on the shortest path from i to j, and y is the cost of the shortest path from i to j.
Write a program that reads a weighted graph representing a network, and finds and outputs the corresponding routing matrix. The routing matrix will be written both to the screen and to an output file. Use Dijkstra’s algorithm to find the shortest cost and path between nodes.
The program runs from the command line with two optional command line arguments. Use the following command line options to indicate the presence of a command line argument: -i (for input file name) and –o (for output file name). If no command line arguments are present, the program uses “xy_input.txt” and “xy_output.txt” as default input and output file names respectively. See examples below:
- java xy_rmatrix
- java xy_rmatrix –i xy_rmatrixi.txt –o xy-rmatrixo.txt
Sample Input/Output: The input file contains zero or more lines representing a graph of a network. Each line represents a bi-directional edge that is made up of two vertices (routers) and the cost associated with the link (communication line) between them. One or more whitespaces (blank, tab, etc.) will separate data on each line and the node names might be a string rather than a single character. Note that the routing matrix rows and columns are listed in alphabetical order.
输入：
输出：
我的主要问题是，对于这个特定问题，是否有必要将输入文件的内容存储在它自己的数据结构中，例如图形或邻接表，我将如何在 Java 与 vertices/nodes 和边缘的方式，我可以执行 Dijsktra 的算法？
我假设指定的路由矩阵与邻接矩阵同义也是正确的吗？
注意：我不是在钓鱼代码，只是朝着正确的方向迈出了一步。
我认为在你的情况下，路由矩阵可以用二维数组表示。
Dijkstra 算法找到从一个源到任何目的地的最短路径。您可以先使用 'A' 作为源，然后使用 'B'，依此类推，根据需要获得从每个点到其他每个点的路由矩阵。您可以再次使用邻接列表或数组来表示图形信息，以便从每个源执行 dijkstra。
希望对您有所帮助！
我一直在研究图论和 Dijsktra，只是发现自己有太多方法可以解决这个问题，而且我不确定该用哪种方法来解决这个特定问题。以下是要求：
In centralized routing, all the routing information is generated and maintained in a centralized location. A common way of maintaining routing information centrally is via a routing matrix. A routing matrix has a row and a column for each node in the network, where a row corresponds to the source node and a column corresponds to the destination node. The entry in row i column j is a pair (x , y), where x is the first node on the shortest path from i to j, and y is the cost of the shortest path from i to j.
Write a program that reads a weighted graph representing a network, and finds and outputs the corresponding routing matrix. The routing matrix will be written both to the screen and to an output file. Use Dijkstra’s algorithm to find the shortest cost and path between nodes. The program runs from the command line with two optional command line arguments. Use the following command line options to indicate the presence of a command line argument: -i (for input file name) and –o (for output file name). If no command line arguments are present, the program uses “xy_input.txt” and “xy_output.txt” as default input and output file names respectively. See examples below:
- java xy_rmatrix
- java xy_rmatrix –i xy_rmatrixi.txt –o xy-rmatrixo.txt
Sample Input/Output: The input file contains zero or more lines representing a graph of a network. Each line represents a bi-directional edge that is made up of two vertices (routers) and the cost associated with the link (communication line) between them. One or more whitespaces (blank, tab, etc.) will separate data on each line and the node names might be a string rather than a single character. Note that the routing matrix rows and columns are listed in alphabetical order.
输入：
输出：
我的主要问题是，对于这个特定问题，是否有必要将输入文件的内容存储在它自己的数据结构中，例如图形或邻接表，我将如何在 Java 与 vertices/nodes 和边缘的方式，我可以执行 Dijsktra 的算法？
我假设指定的路由矩阵与邻接矩阵同义也是正确的吗？
注意：我不是在钓鱼代码，只是朝着正确的方向迈出了一步。
我认为在你的情况下，路由矩阵可以用二维数组表示。 Dijkstra 算法找到从一个源到任何目的地的最短路径。您可以先使用 'A' 作为源，然后使用 'B'，依此类推，根据需要获得从每个点到其他每个点的路由矩阵。您可以再次使用邻接列表或数组来表示图形信息，以便从每个源执行 dijkstra。
希望对您有所帮助！