Warm tip: This article is reproduced from serverfault.com, please click

make dijkstra algorithm take input from .txt file in python

发布于 2020-11-28 22:59:55

i'm trying to make this dijkstra algorithm take input for "testedges' from a text file (vertices.txt) so I want 'testedges = myedges' to work without errors. and make the user enters the two vertices that he wants to know the shortest path between, so I need to use input() and don't manually write the two nodes in the code like it's shown below in the full code.

The full code:

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"))

the adjustment I want are :

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 is formatted this way

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

note:

Questioner
Ryu
Viewed
0
Shivam Miglani 2020-11-29 18:14:27

For file which contains edges like:

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

You can do something like:

# 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)

Some general advice:

  • Use descriptive, readable variable names (e.g. not myarray)
  • read python docs for standard functionality that Python provides for strings and files (split(), strip(), input()and open()). It allows you to do more in less lines of code and has nice examples of doing such things.