Shortest Path Analysis in Transport Networks

Analyzing shortest paths and critical nodes in a transport network using NetworkX

Python
import networkx as nx
import matplotlib.pyplot as plt
import random

# Create a sample transport network
G = nx.Graph()
cities = ['New York', 'Los Angeles', 'Chicago', 'Houston', 'Phoenix', 'Philadelphia', 'San Antonio', 'San Diego', 'Dallas', 'San Jose']
for city in cities:
    G.add_node(city)

# Add edges with random weights (distances)
for i in range(len(cities)):
    for j in range(i + 1, len(cities)):
        weight = random.randint(100, 1000)
        G.add_edge(cities[i], cities[j], weight=weight)

# Find the shortest path between two cities
start = 'New York'
end = 'Los Angeles'
shortest_path = nx.shortest_path(G, start, end, weight='weight')
shortest_path_length = nx.shortest_path_length(G, start, end, weight='weight')

print(f"Shortest path from {start} to {end}:")
print(" -> ".join(shortest_path))
print(f"Total distance: {shortest_path_length}")

# Identify critical nodes (articulation points)
critical_nodes = list(nx.articulation_points(G))
print("\nCritical nodes (articulation points):")
print(", ".join(critical_nodes))

# Calculate and print betweenness centrality
betweenness_centrality = nx.betweenness_centrality(G, weight='weight')
print("\nBetweenness Centrality (Top 3 cities):")
for city, centrality in sorted(betweenness_centrality.items(), key=lambda x: x[1], reverse=True)[:3]:
    print(f"{city}: {centrality:.3f}")

# Visualize the network
pos = nx.spring_layout(G)
plt.figure(figsize=(12, 8))
nx.draw(G, pos, with_labels=True, node_color='lightgreen', node_size=700, font_size=8, font_weight='bold')
nx.draw_networkx_nodes(G, pos, nodelist=critical_nodes, node_color='red', node_size=700)

# Draw edge labels
edge_labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_size=6)

# Highlight the shortest path
path_edges = list(zip(shortest_path, shortest_path[1:]))
nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color='r', width=2)

plt.title("Transport Network with Shortest Path and Critical Nodes")
plt.axis('off')
plt.tight_layout()
plt.show()

Related