使用NetworkX求解TSP时出现KeyError:1的问题解决

问题 #

我编写了一段代码，用于生成10个随机图并使用NetworkX求解旅行商问题（TSP），但运行时出现了KeyError: 1错误。以下是我的代码：

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
import time
import csv
import pandas as pd

# Function to generate a random graph
def generate_random_graph(num_nodes, edge_prob):
    return nx.erdos_renyi_graph(num_nodes, edge_prob)

# Function to solve TSP and track time
def solve_tsp(graph):
    start_time = time.time()
    cycle = nx.algorithms.approximation.traveling_salesman_problem(graph, cycle=True)
    end_time = time.time()
    elapsed_time = end_time - start_time
    return cycle, elapsed_time

# Number of nodes in the graph
num_nodes = 10

data_points = []
csv_data = []

# Generate 10 random graphs, solve TSP, and record data
for i in range(10):
    edge_prob = np.random.rand()  # Random edge probability
    graph = generate_random_graph(num_nodes, edge_prob)
    density = nx.density(graph)
    
    # Solve TSP
    cycle, elapsed_time = solve_tsp(graph)
    
    # Record data
    data_points.append((density, elapsed_time))
    
    # Prepare adjacency matrix for CSV
    adj_matrix = nx.adjacency_matrix(graph).todense().tolist()
    
    csv_data.append([adj_matrix, density, elapsed_time, cycle])

运行后出现如下报错信息：

KeyError                                  Traceback (most recent call last)
Cell In[7], line 8
      5 density = nx.density(graph)
      7 # Solve TSP
----> 8 cycle, elapsed_time = solve_tsp(graph)
     10 # Record data
     11 data_points.append((density, elapsed_time))

Cell In[3], line 4, in solve_tsp(graph)
      2 def solve_tsp(graph):
      3     start_time = time.time()
----> 4     cycle = nx.algorithms.approximation.traveling_salesman_problem(graph, cycle=True)
      5     end_time = time.time()
      6     elapsed_time = end_time - start_time

File ~/anaconda3/envs/py39/lib/python3.9/site-packages/networkx/utils/backends.py:412, in _dispatch.__call__(self, backend, *args, **kwargs)
    409 def __call__(self, /, *args, backend=None, **kwargs):
    410     if not backends:
    411         # Fast path if no backends are installed
--> 412         return self.orig_func(*args, **kwargs)
    414     # Use `backend_name` in this function instead of `backend`
    415     backend_name = backend

File ~/anaconda3/envs/py39/lib/python3.9/site-packages/networkx/algorithms/approximation/traveling_salesman.py:320, in traveling_salesman_problem(G, weight, nodes, cycle, method)
    318         if u == v:
    319             continue
--> 320         GG.add_edge(u, v, weight=dist[u][v])
    321 best_GG = method(GG, weight)
    323 if not cycle:
    324     # find and remove the biggest edge

KeyError: 1

请问该如何解决这个错误？

解决方案 #

错误原因 #

NetworkX的TSP近似算法要求输入的图必须是连通图，但erdos_renyi_graph生成的随机图可能因边概率过低出现孤立节点或多个连通分量。算法计算节点间最短路径时，无法找到不连通节点的路径，从而抛出KeyError。

解决步骤 #

1. 确保生成连通图：修改图生成函数，循环生成直到得到连通图。
2. 可选：添加边权重：原始图无权重，算法默认将边权重视为1，显式添加权重能让TSP问题更符合实际场景。

修改后的代码如下：

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
import time
import csv
import pandas as pd

# Function to generate a connected random graph
def generate_random_graph(num_nodes, edge_prob):
    while True:
        graph = nx.erdos_renyi_graph(num_nodes, edge_prob)
        # 检查图是否连通
        if nx.is_connected(graph):
            # 为每条边添加随机权重（可选）
            for (u, v) in graph.edges():
                graph.edges[u, v]['weight'] = np.random.randint(1, 100)
            return graph

# Function to solve TSP and track time
def solve_tsp(graph):
    start_time = time.time()
    cycle = nx.algorithms.approximation.traveling_salesman_problem(graph, cycle=True)
    end_time = time.time()
    elapsed_time = end_time - start_time
    return cycle, elapsed_time

# Number of nodes in the graph
num_nodes = 10

data_points = []
csv_data = []

# Generate 10 random graphs, solve TSP, and record data
for i in range(10):
    # 限制边概率范围，避免生成连通图耗时过长
    edge_prob = np.random.uniform(0.3, 1.0)  
    graph = generate_random_graph(num_nodes, edge_prob)
    density = nx.density(graph)
    
    # Solve TSP
    cycle, elapsed_time = solve_tsp(graph)
    
    # Record data
    data_points.append((density, elapsed_time))
    
    # Prepare adjacency matrix for CSV
    adj_matrix = nx.adjacency_matrix(graph).todense().tolist()
    
    csv_data.append([adj_matrix, density, elapsed_time, cycle])

额外说明 #

• 把边概率范围设为0.3-1.0，可以减少生成连通图的循环次数，提升效率——过低的边概率很难生成连通图。
• 如果不需要边权重，直接删掉添加权重的代码块即可，算法会自动将每条边权重视为1。

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