使 dijkstra 算法从 python 中的 .txt 文件中获取输入

Question

我正在尝试让这个 dijkstra 算法从文本文件 (vertices.txt) 中获取“testedges”的输入，所以我希望 'testedges = myedges' 能够正常工作。并让用户输入他想知道两个顶点之间的最短路径，所以我需要使用 input() 而不是在代码中手动编写两个节点，如下面的完整代码所示。

完整代码：

from collections import defaultdict
from heapq import *

def dijkstra(edges, f, t):
  

    return float("inf")
if __name__ == "__main__":
    testedges = [
        ("A", "B", 7),
        ("A", "D", 5),
        ("B", "C", 8),
        ("B", "D", 9),
        ("B", "E", 7),
        ("C", "E", 5),
        ("D", "E", 15),
        ("D", "F", 6),
        ("E", "F", 8),
        ("E", "G", 9),
        ("F", "G", 11)
    ]

    print("=== Dijkstra ===")
    print (testedges)
    print ("A -> E:")
    print (dijkstra(testedges, 'A', 'E'))
    print ("F -> G:")
    print (dijkstra(testedges, "F", "G"))

我想要的调整是：

testedges = myedges        # meanning that I want the edges to come straight from the .txt file 
print (input() ,"->" ,input()) # get the shortest path for the two nodes user chooses
 print (dijkstra(myedges, input(), input())

.txt 的格式是这样的

4,3,10 // i, j, k tells you that there is an edge between vi and vj and its 
          weight is k.
2,1,4  // v1,v2,5 and so on for the rest 
1,3,2
3,4,3
0,2,30

注：

Answer 1

一个可能的解决方案是：

一个名为 dijkstra.config 的配置文件，包含以下内容：

[PARAMETERS]
node_numbers: 5
coordinates: (1, 10),(8, 10),(10, 8),(7, 4),(3, 1)
nodes: (0,1,10),(1,2,5),(2,3,25),(0,3,3),(3,4,8)

您可以在 python 文件 test.py 中检查如何使用它运行以下代码：

import configparser

config = configparser.ConfigParser()
config.read("dijkstra.config")

print("number of nodes:\n" ,config["PARAMETERS"]["node_numbers"])
print("coordinates:\n", config["PARAMETERS"]["coordinates"])
print("nodes:\n", config["PARAMETERS"]["nodes"])

Answer 2

对于包含如下边缘的文件：

A,B,7
C,D,8
...

你可以这样做：

# 1. Reading edge info from the file 
with open("vertices.txt") as f:
    lines = f.readlines()
    # store ordered pair of node 1, node2 and integer distance in a list
    my_edges = []
    for line in lines:
        node1, node2, distance = (line.strip().split(','))
        my_edges.append((node1,node2, int(distance)))
# similarly you can read other information like coordinates.

test_edges = my_edges

# 2. taking string input from user. 
# As input required is string, we don't need to typecast
print("Enter start node")
start_node = input()
print("Enter end node")
end_node = input()

# 3. call function that returns shortest path
shortest_path = dijkstra(test_edges, start_node, end_node)

一些一般性建议：

使用描述性的、可读的变量名（例如不是 myarray）
阅读 python 文档了解 Python 为字符串和文件提供的标准功能（split()、strip()、input() 和 open() ).它允许您用更少的代码行做更多的事情，并且有很好的例子来做这些事情。

使 dijkstra 算法从 python 中的 .txt 文件中获取输入

make dijkstra algorithm take input from .txt file in python

python

algorithm

dijkstra