Python中基于最短路径的数据分析与应用

import heapq

graph = {'pidancode.com': {'皮蛋编程': 6, 'Python': 2},
         'Python': {'pidancode.com': 2, 'Java': 3, 'JavaScript': 3},
         'JavaScript': {'Python': 3, '皮蛋编程': 7},
         'Java': {'Python': 3, '皮蛋编程': 5},
         '皮蛋编程': {'pidancode.com': 6, 'JavaScript': 7, 'Java': 5}}

def dijkstra(graph, start, end):
    # dist记录起点到各个点的最短距离
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    # Heapq是一个小根堆，存储未被访问的节点
    pq = [(0, start)]
    while pq:
        (distance, node) = heapq.heappop(pq)
        if distance > dist[node]:
            continue
        for neighbor, weight in graph[node].items():
            new_dist = dist[node] + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))
    return dist[end]

print(dijkstra(graph, 'pidancode.com', '皮蛋编程'))    # 输出4

import numpy as np

# 定义邻接矩阵
graph = np.array([
    [0, 2, np.inf, np.inf, 6],
    [2, 0, 3, 5, np.inf],
    [np.inf, 3, 0, 7, np.inf],
    [np.inf, 5, 7, 0, 1],
    [6, np.inf, np.inf, 1, 0]
])

def floyd(graph):
    # dist记录任意两点的最短距离
    dist = graph.copy()
    n = len(graph)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                # 如果经过k点，路径更短，则更新最短路径
                if dist[i, k] + dist[k, j] < dist[i, j]:
                    dist[i, j] = dist[i, k] + dist[k, j]
    return dist

print(floyd(graph))    # 输出任意两点之间的最短路径