您正在寻找 Dijkstra 的最短路径算法。巧合的是，就在本周，我用 Python 实现了这个。实现有点重（因为我的目标是展示如何使用unittest执行单元测试），但它仍然有效。Dijkstra 的算法适用于有向图，但您可以通过为每个无向边创建A -> B和有向边将无向图转换为有向图，就像您所做的那样。B -> AA -- B
from collections import defaultdict
from itertools import product, chain
class DijkstraNegativeWeightException(Exception):
pass
class DijkstraDisconnectedGraphException(Exception):
pass
class Dijkstra:
def __init__(self, graph_data, source):
self._graph = defaultdict(dict, graph_data)
self._check_edge_weights()
self.reset_source(source)
self._solved = False
@property
def edges(self):
return [(i, j) for i in self._graph for j in self._graph[i]]
@property
def nodes(self):
return list(set(chain(*self.edges)))
def _check_source_in_nodes(self):
msg = 'Source node \'{}\' not in graph.'
if self._source not in self.nodes:
raise ValueError(msg.format(self._source))
def _check_edge_weights(self):
msg = 'Graph has negative weights, but weights must be non-negative.'
if any(self._graph[i][j] < 0 for (i, j) in self.edges):
raise DijkstraNegativeWeightException(msg)
def reset_source(self, source):
self._source = source
self._check_source_in_nodes()
self._solution_x = []
self._solution_z = {source: 0}
self._visited = set([source])
self._unvisited = set()
for key, val in self._graph.items():
self._unvisited.add(key)
self._unvisited.update(val.keys())
self._unvisited.difference_update(self._visited)
self._solved = False
def run(self):
weight_candidates = self._graph[self._source].copy()
node_candidates = dict(product(weight_candidates.keys(),
(self._source,)))
while node_candidates:
j = min(weight_candidates, key=weight_candidates.get)
weight_best, i = weight_candidates.pop(j), node_candidates.pop(j)
for k in self._graph[j].keys() & self._unvisited:
weight_next = self._graph[j][k]
if (k not in node_candidates
or weight_candidates[k] > weight_best + weight_next):
weight_candidates[k] = weight_best + weight_next
node_candidates[k] = j
self._solution_x.append((i, j))
self._solution_z[j] = weight_best
self._visited |= {j}
self._unvisited -= {j}
self._solved = True
def path_to(self, target):
if self._source in self._visited and target in self._unvisited:
msg = 'No path from {} to {}; graph is disconnected.'
msg = msg.format(self._visited, self._unvisited)
raise DijkstraDisconnectedGraphException(msg)
solution = self._solution_x.copy()
path = []
while solution:
i, j = solution.pop()
if j == target:
path.append((i, j))
break
while solution:
i_prev, _, i, j = *path[-1], *solution.pop()
if j == i_prev:
path.append((i, j))
if i == self._source:
break
return list(reversed(path)), self._solution_z[target]
def visualize(self, source=None, target=None):
import networkx as nx
import matplotlib.pyplot as plt
if (source is not None and source != self._source):
self.reset_source(source)
if not self._solved:
self.run()
if target is not None:
path, _ = self.path_to(target=target)
else:
path = self._solution_x
edgelist = self.edges
nodelist = self.nodes
nxgraph = nx.DiGraph()
nxgraph.add_edges_from(edgelist)
weights = {(i, j): self._graph[i][j] for (i, j) in edgelist}
found = list(chain(*path))
ncolors = ['springgreen' if node in found else 'lightcoral'
for node in nodelist]
ecolors = ['dodgerblue' if edge in path else 'black'
for edge in edgelist]
sizes = [3 if edge in path else 1 for edge in edgelist]
pos = nx.kamada_kawai_layout(nxgraph)
nx.draw_networkx(nxgraph, pos=pos,
nodelist=nodelist, node_color=ncolors,
edgelist=edgelist, edge_color=ecolors, width=sizes)
nx.draw_networkx_edge_labels(nxgraph, pos=pos, edge_labels=weights)
plt.axis('equal')
plt.show()
对于您的图表（添加了权重），
graph_data = {
"A": {"B": 1, "C": 1, "E": 1},
"B": {"A": 1, "D": 1, "E": 1},
"C": {"A": 1, "F": 1, "G": 1},
"D": {"B": 1},
"E": {"A": 1, "B": 1,"D": 1},
"F": {"C": 1},
"G": {"C": 1}
}
algo = Dijkstra(graph_data, source='A')
algo.run() # creates a shortest-path tree (SPT) to all reachable nodes
x, z = algo.path_to('G')
print(x)
print(z)
algo.visualize(source='A', target='G')
输出（遍历的边和这些边的组合权重）。
[('A', 'C'), ('C', 'G')]
2
可视化对于无向图来说看起来很粗糙，但它仍然为您提供了解决方案的要点。
