如何实现Python版Dijkstra算法从TXT读边并支持用户输入顶点

Got it, let's fix up your Dijkstra algorithm code to meet those two requirements. Here's the complete working version, plus a breakdown of what changed:

import heapq

def dijkstra(graph, start, end):
    # Initialize distance dict: all nodes start at infinity, except the start node
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    # Priority queue to track (current distance, node)
    priority_queue = [(0, start)]
    # Track predecessors to reconstruct the path later
    predecessors = {node: None for node in graph}

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        # Early exit if we've reached the end node
        if current_node == end:
            break

        # Skip if we've already found a shorter path to this node
        if current_distance > distances[current_node]:
            continue

        # Iterate through all neighbors of the current node
        for neighbor, weight in graph[current_node].items():
            new_distance = current_distance + weight
            # Update distance if we found a shorter path
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                predecessors[neighbor] = current_node
                heapq.heappush(priority_queue, (new_distance, neighbor))

    # Reconstruct the shortest path from end to start, then reverse it
    path = []
    current = end
    while current is not None:
        path.append(current)
        current = predecessors[current]
    path.reverse()

    return distances[end], path

def load_graph_from_file(file_path):
    graph = {}
    with open(file_path, 'r') as f:
        for line in f:
            # Skip empty lines and strip whitespace
            cleaned_line = line.strip()
            if not cleaned_line:
                continue
            # Split line into vertex i, vertex j, and weight k
            i, j, k = cleaned_line.split(',')
            node_i = int(i)
            node_j = int(j)
            weight = int(k)
            # Add bidirectional edge (adjust to unidirectional if your graph is directed)
            if node_i not in graph:
                graph[node_i] = {}
            graph[node_i][node_j] = weight
            if node_j not in graph:
                graph[node_j] = {}
            graph[node_j][node_i] = weight
    return graph

if __name__ == "__main__":
    # Load edges from vertices.txt into myedges
    myedges = load_graph_from_file('vertices.txt')
    # Replace testedges with myedges as requested
    testedges = myedges

    # Get valid start and end vertices from user input
    while True:
        try:
            start = int(input("Enter the start vertex number: "))
            end = int(input("Enter the end vertex number: "))
            # Check if vertices exist in the graph
            if start not in testedges or end not in testedges:
                print("That vertex doesn't exist in the graph. Please try again.")
                continue
            break
        except ValueError:
            print("Please enter a valid integer for the vertex number.")

    # Calculate and print the shortest path
    shortest_dist, shortest_path = dijkstra(testedges, start, end)
    print(f"Shortest distance from vertex {start} to {end}: {shortest_dist}")
    print("Shortest path:", " -> ".join(map(str, shortest_path)))

Key Changes Explained: #

• Loading edges from vertices.txt:

  • Added the load_graph_from_file function to parse the text file line by line. It builds a dictionary-based graph where each node maps to its neighbors and edge weights.
  • Handles empty lines in the file and converts the input strings to integers for proper graph construction.
  • Sets testedges = myedges directly, so no issues with the replacement.

• User-input start/end vertices:

  • Added input validation to catch non-integer inputs and vertices that aren't present in the graph.
  • Uses a loop to keep asking for input until valid values are provided, preventing runtime errors.

• Extra Quality-of-Life Tweak:

  • Added path reconstruction so the code not only returns the shortest distance but also the actual path taken between the start and end vertices.

Just make sure your vertices.txt is in the same directory as the code, with lines formatted exactly like i,j,k (e.g., 0,1,5 for an edge between vertex 0 and 1 with weight 5).

内容的提问来源于stack exchange，提问作者Ryu