Python实现最短路径问题的常用库

import networkx as nx
import matplotlib.pyplot as plt

# 创建图并添加边
G = nx.Graph()
G.add_edge('A', 'B', weight=2)
G.add_edge('B', 'C', weight=1)
G.add_edge('C', 'D', weight=3)
G.add_edge('D', 'E', weight=4)
G.add_edge('E', 'F', weight=2)
G.add_edge('F', 'G', weight=1)
G.add_edge('G', 'H', weight=3)
G.add_edge('H', 'A', weight=2)

# 计算最短路径并展示结果
path = nx.dijkstra_path(G, 'A', 'G')
print('Shortest path:', path)
pos = nx.spring_layout(G)
nx.draw_networkx_nodes(G, pos)
nx.draw_networkx_edges(G, pos)
nx.draw_networkx_labels(G, pos)
nx.draw_networkx_edge_labels(G, pos, edge_labels=nx.get_edge_attributes(G, 'weight'))
nx.draw_networkx_edges(G, pos, edgelist=[(path[i], path[i+1]) for i in range(len(path)-1)], edge_color='blue', width=5)
plt.axis('off')
plt.show()

import numpy as np
import scipy.sparse as sp
from scipy.sparse.csgraph import dijkstra

# 创建图的邻接矩阵表示
graph = np.array([[0, 2, 0, 0, 0, 0, 0, 2],
                  [2, 0, 1, 0, 0, 0, 0, 0],
                  [0, 1, 0, 3, 0, 0, 0, 0],
                  [0, 0, 3, 0, 4, 1, 0, 0],
                  [0, 0, 0, 4, 0, 2, 0, 0],
                  [0, 0, 0, 1, 2, 0, 5, 0],
                  [0, 0, 0, 0, 0, 5, 0, 3],
                  [2, 0, 0, 0, 0, 0, 3, 0]])
csr_graph = sp.csr_matrix(graph)

# 计算最短路径并展示结果
distances, predecessors = dijkstra(csr_graph, indices=0, return_predecessors=True)
path = [7]
while path[-1] != 0:
    path.append(predecessors[path[-1]])
path.reverse()
print('Shortest path:', path)
print('Distance:', distances[7])

import igraph

# 创建图并添加边
g = igraph.Graph(directed=True)
g.add_vertices(8)
g.add_edges([(0, 1), (0, 7), (1, 2), (1, 5), (2, 3), (3, 4), (4, 2), (4, 5), (4, 6), (6, 7), (7, 5)])
g.es['weight'] = [1, -2, 3, 4, 5, 6, 2, 1, -8, -1, 1]

# 计算最短路径并展示结果
path = g.shortest_paths_dijkstra(source=0, target=5, weights='weight', return_path=True)
print('Shortest path:', path[0])
print('Distance:', path[1])