不使用Networkx的Python图冗余节点求解方案咨询

Got it, let's break this down without relying on NetworkX. The core problem here is identifying redundant edges—those that don't contribute to the shortest path from a node to the target (node 1) in your directed graph. Here's a step-by-step approach you can implement with basic Python tools:

1. Represent the Graph with Basic Data Structures #

First, use a Python dictionary to store your graph. Keys are node numbers, and values are lists of nodes they point to (or tuples of (neighbor, weight) if you're working with weighted edges, which fits your "distance closer" description).

For your specific problem, here's how to define it (we'll use weighted edges to match the "distance closer" logic):

# Weighted graph where:
# - 3→1 has a higher weight (longer path) than 3→5→1
# - 4→1 has a higher weight than 4→2→1
weighted_graph = {
    1: [],          # No outgoing edges
    2: [(1, 1)],    # Points only to 1 (weight 1)
    3: [(1, 3), (5, 1)],  # Points to 1 (weight 3) and 5 (weight 1)
    4: [(1, 3), (2, 1)],  # Points to 1 (weight 3) and 2 (weight 1)
    5: [(1, 1)]     # Points to 1 (weight 1)
}

2. Calculate Shortest Distances to the Target Node #

Since we need to find which edges lead to the shortest path to node 1, we'll compute the shortest distance from every node to 1. For weighted graphs, we can implement a simplified version of Dijkstra's algorithm (perfect for small graphs like this):

def compute_weighted_shortest_distances(target_node, graph):
    # Initialize distances: set all to infinity except the target (distance 0)
    distances = {node: float('inf') for node in graph}
    distances[target_node] = 0
    unvisited = list(graph.keys())

    while unvisited:
        # Pick the unvisited node with the smallest current distance
        current_node = min(unvisited, key=lambda x: distances[x])
        unvisited.remove(current_node)

        # Skip if this node is unreachable
        if distances[current_node] == float('inf'):
            break

        # Update distances for nodes pointing to current_node (reverse traversal)
        for neighbor, weight in graph[current_node]:
            if distances[neighbor] > distances[current_node] + weight:
                distances[neighbor] = distances[current_node] + weight

    return distances

# Get shortest distances from each node to 1
shortest_distances = compute_weighted_shortest_distances(1, weighted_graph)
print("Shortest distances to node 1:", shortest_distances)
# Output: {1: 0, 2: 1, 3: 2, 4: 2, 5: 1}

For unweighted graphs, you could use BFS instead—it's faster and simpler for equal-weight edges.

3. Filter Out Redundant Edges #

Now we'll check each edge: if taking that edge keeps us on a shortest path to node 1, we keep it; otherwise, it's redundant.

def filter_redundant_edges(graph, shortest_distances, target_node):
    non_redundant_graph = {node: [] for node in graph}
    redundant_edges = []

    for node, edges in graph.items():
        for neighbor, weight in edges:
            # Check if this edge is part of a shortest path
            if shortest_distances[node] == shortest_distances[neighbor] + weight:
                non_redundant_graph[node].append((neighbor, weight))
            else:
                redundant_edges.append((node, neighbor))

    return non_redundant_graph, redundant_edges

# Get the cleaned graph and list of redundant edges
clean_graph, redundant = filter_redundant_edges(weighted_graph, shortest_distances, 1)
print("\nNon-redundant graph (only shortest path edges):", clean_graph)
print("Redundant edges:", redundant)
# Output:
# Non-redundant graph: {1: [], 2: [(1, 1)], 3: [(5, 1)], 4: [(2, 1)], 5: [(1, 1)]}
# Redundant edges: [(3, 1), (4, 1)]

This matches exactly what you described: the direct edges from 3→1 and 4→1 are marked as redundant, since paths through 5 and 2 respectively are shorter.

Key Takeaways #

You don't need NetworkX for this—basic Python data structures and a manual implementation of shortest path logic are more than enough for small graphs like this. The core idea is:

• Represent the graph clearly with dictionaries/lists
• Calculate shortest distances to your target node
• Keep only edges that contribute to those shortest paths

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