Java实现带负权值加权图中两节点最短路径求解问题

Hey there! Let's break down how to optimize the Bellman-Ford algorithm for your specific problem—since you only care about the shortest path from a source to a single target (not all nodes), we can cut out a lot of unnecessary work and even add early termination logic to speed things up.

Your core goal is simple: check if there’s a path from the source to the target with a total weight below a given threshold. Standard Bellman-Ford wastes cycles calculating distances to every node, so here are targeted optimizations:

1. Early Termination Checks #

The standard Bellman-Ford runs V-1 full iterations of edge relaxation, but you can stop early in two key scenarios:

• Target meets the threshold: As soon as the shortest distance to the target node drops below your maximum allowed cost, you can immediately return 1—no need to keep computing.
• No more updates: If an entire iteration passes without any node’s distance being updated, all possible shortest paths have been found. You can stop here and just check the target’s final distance.

2. Queue-Based Optimization (SPFA Algorithm) #

The Shortest Path Faster Algorithm (SPFA) is an optimized variant of Bellman-Ford that only relaxes edges from nodes whose distance was recently updated. This drastically reduces redundant work, especially on sparse graphs. For your use case, we can add extra shortcuts:

• Stop and return 1 the moment the target’s distance falls below the threshold.
• Skip any nodes that can’t possibly reach the target (we’ll cover how to do this with reverse graphs next).

Step-by-Step SPFA Implementation (Matching Your Input Format) #

Here’s a practical, human-readable implementation outline:

import queue

def check_valid_path():
    # Parse input
    source, target, max_cost = input().split()
    source = int(source)
    target = int(target)
    max_cost = float(max_cost)

    # Edge case: source == target
    if source == target:
        return 1 if 0 < max_cost else 0

    node_count, edge_count = input().split()
    node_count = int(node_count)
    edge_count = int(edge_count)

    # Build adjacency list for the graph
    adjacency = [[] for _ in range(node_count)]
    for _ in range(edge_count):
        edge_part, weight = input().strip().split()
        u, v = edge_part.split('→')
        adjacency[int(u)].append( (int(v), float(weight)) )

    # Initialize distance tracking
    INF = float('inf')
    distances = [INF] * node_count
    distances[source] = 0
    in_queue = [False] * node_count
    update_queue = queue.Queue()
    update_queue.put(source)
    in_queue[source] = True

    # Track enqueue count to detect negative cycles
    enqueue_count = [0] * node_count
    enqueue_count[source] = 1

    while not update_queue.empty():
        current_node = update_queue.get()
        in_queue[current_node] = False

        for neighbor, edge_weight in adjacency[current_node]:
            if distances[neighbor] > distances[current_node] + edge_weight:
                distances[neighbor] = distances[current_node] + edge_weight

                # Check if we've hit the target with a valid cost
                if neighbor == target and distances[neighbor] < max_cost:
                    return 1

                # Add neighbor to queue if not already present
                if not in_queue[neighbor]:
                    enqueue_count[neighbor] += 1
                    # Detect negative cycle: if a node is enqueued > V times, it's in a cycle
                    if enqueue_count[neighbor] > node_count:
                        # If this cycle is on a path from source to target, we can loop infinitely to lower cost
                        # For simplicity, return 1 here (since we can always get cost below the threshold)
                        return 1
                    update_queue.put(neighbor)
                    in_queue[neighbor] = True

    # After processing all possible updates, check final target distance
    return 1 if distances[target] < max_cost else 0

# Run the function
print(check_valid_path())

3. Reverse Graph Pruning (For Large Graphs) #

If you’re working with a huge graph, you can pre-filter nodes that can’t possibly reach the target:

1. Build a reverse graph where all edge directions are flipped (e.g., an edge u→v becomes v→u).
2. Use BFS or DFS starting from the target to find all nodes that can reach the target in the original graph.
3. In your SPFA/Bellman-Ford run, only process these nodes and their edges—ignore everything else. This cuts down on unnecessary computations significantly.

Handling Edge Cases #

• Unreachable target: If the target isn’t reachable from the source (verified via reverse graph BFS/DFS), return 0 immediately.
• Negative cycles: If there’s a negative cycle on a path from source to target, you can loop the cycle infinitely to make the total cost as low as needed. Detect this (via enqueue counts in SPFA) and return 1.

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