将图转换为字典格式：Dijkstra算法开发中的图格式适配问题

Got it, let's tackle this conversion step by step. Your current graph structure stores nodes in the first sublist and edges as unordered node-pair sets with weights in the second. Here's a straightforward Python solution to turn it into the adjacency dictionary format you need for Dijkstra's algorithm:

Code Implementation #

G = [['a', 'b' , 'c' , 'd' , 'e' , 'f' , 'g' , 'h', 'i', 'j'], [({'a', 'b'}, 4), ({'a', 'c'}, 6), ({'a', 'd'}, 8), ({'b', 'e'}, 1) , ({'b', 'f'}, 9), ({'c', 'f'}, 2), ({'d', 'g'}, 7), ({'d', 'h'}, 1) , ({'e', 'i'}, 2), ({'e', 'j'}, 7), ({'g', 'h'}, 2), ({'i', 'j'}, 4)]]

# Initialize adjacency dict with empty entries for each node
adjacency_dict = {node: {} for node in G[0]}

# Process each edge to populate the dict
for edge_nodes, weight in G[1]:
    # Convert the unordered set to a list to access both nodes
    u, v = list(edge_nodes)
    # Add bidirectional edges (since your graph uses unordered node pairs)
    adjacency_dict[u][v] = weight
    adjacency_dict[v][u] = weight

# Check the result (optional)
print(adjacency_dict['a'])  # Output: {'b': 4, 'c': 6, 'd': 8}
print(adjacency_dict['b'])  # Output: {'a': 4, 'e': 1, 'f': 9}

How It Works #

• Initialize the Dictionary: We use a dictionary comprehension to create a base structure where every node from your first sublist has an empty dictionary as its value. This sets up the framework for storing adjacent nodes and weights.
• Process Each Edge: For every edge entry, we convert the unordered set of nodes into a list so we can grab both endpoints (u and v). Since your edges are stored as unordered sets, this assumes it's an undirected graph—so we add the weight to both u's entry for v and v's entry for u. If you actually need a directed graph, just remove the line adjacency_dict[v][u] = weight.
• Verify the Output: The print statements show that the resulting dictionary matches the format you specified, making it perfect for implementing Dijkstra's algorithm.

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