Python中如何实现最短路径查找算法
在Python中，最短路径查找算法可以通过Dijkstra算法或BFS算法来实现。
Dijkstra算法基于贪心思想，每次选择当前节点到起点距离最短的节点进行扩展，直到扩展到终点或者所有节点都被扩展。具体实现可以使用一个优先队列来存储未被扩展的节点，并记录每个节点到起点的距离。下面是使用Dijkstra算法查找“pidancode.com”到“皮蛋编程”的最短路径的代码：
import heapq def dijkstra(graph, start, end): """ 使用Dijkstra算法查找图中 start 到 end 的最短路径 :param graph: 图，使用字典表示，如 {'a': {'b': 2, 'c': 3}, 'b': {'c': 1, 'd': 4}, 'c': {'d': 2}, 'd': {}} :param start: 起点 :param end: 终点 :return: 最短路径，如 ['a', 'b', 'c', 'd'] """ distances = {node: float('inf') for node in graph} # 初始化起点到每个节点的距离为无穷 distances[start] = 0 # 起点到自身的距离为0 queue = [(0, start)] # 使用优先队列存储未被扩展的节点，每次取最小值进行扩展 while queue: (curr_dist, curr_node) = heapq.heappop(queue) # 取出当前到起点距离最短的节点进行扩展 if curr_node == end: # 终点被扩展到，返回最短路径 path = [] while curr_node != start: path.append(curr_node) curr_node = parents[curr_node] path.append(start) return path[::-1] for (neighbor, weight) in graph[curr_node].items(): # 扩展邻居节点 distance = curr_dist + weight if distance < distances[neighbor]: distances[neighbor] = distance parents[neighbor] = curr_node heapq.heappush(queue, (distance, neighbor)) return None # 没有找到最短路径 # 例子：查找 "pidancode.com" 到 "皮蛋编程" 的最短路径 graph = { "pidancode.com": {"baidu.com": 1, "zhihu.com": 2, "google.com": 4}, "baidu.com": {"pidancode.com": 1, "zhihu.com": 3, "so.com": 2}, "zhihu.com": {"baidu.com": 3, "pidancode.com": 2, "google.com": 3}, "so.com": {"baidu.com": 2}, "google.com": {"pidancode.com": 4, "zhihu.com": 3}, "皮蛋编程": {} } parents = {} path = dijkstra(graph, "pidancode.com", "皮蛋编程") print(path)
BFS算法则遍历图中所有节点，记录每个节点到起点的距离，并逐步扩展距离更远的节点，直到到达终点或者所有节点都被扩展。下面是使用BFS算法查找“pidancode.com”到“皮蛋编程”的最短路径的代码：
from collections import deque def bfs(graph, start, end): """ 使用BFS算法查找图中 start 到 end 的最短路径 :param graph: 图，使用字典表示，如 {'a': {'b': 1, 'c': 2}, 'b': {'c': 1, 'd': 3}, 'c': {'d': 1}, 'd': {}} :param start: 起点 :param end: 终点 :return: 最短路径，如 ['a', 'b', 'c', 'd'] """ distances = {node: float('inf') for node in graph} # 初始化起点到每个节点的距离为无穷 distances[start] = 0 # 起点到自身的距离为0 parents = {start: None} # 记录每个节点的父节点 queue = deque([start]) # 使用队列存储等待扩展的节点 while queue: current_node = queue.popleft() if current_node == end: # 终点被扩展到，返回最短路径 path = [] while current_node != start: path.append(current_node) current_node = parents[current_node] path.append(start) return path[::-1] for neighbor in graph[current_node].keys(): # 扩展邻居节点 if distances[neighbor] == float('inf'): distances[neighbor] = distances[current_node] + 1 parents[neighbor] = current_node queue.append(neighbor) return None # 没有找到最短路径 # 例子：查找 "pidancode.com" 到 "皮蛋编程" 的最短路径 graph = { "pidancode.com": {"baidu.com": 1, "zhihu.com": 2, "google.com": 4}, "baidu.com": {"pidancode.com": 1, "zhihu.com": 3, "so.com": 2}, "zhihu.com": {"baidu.com": 3, "pidancode.com": 2, "google.com": 3}, "so.com": {"baidu.com": 2}, "google.com": {"pidancode.com": 4, "zhihu.com": 3}, "皮蛋编程": {} } path = bfs(graph, "pidancode.com", "皮蛋编程") print(path)
相关文章