最短路径算法的Python实现与可视化

# 定义一个字符串作为图
graph = {
    'pidancode.com': {'coding.net':1, 'github.com':2},
    'coding.net': {'pidancode.com':1, 'github.com':1},
    'github.com': {'pidancode.com':2, 'coding.net':1}
}

# 定义Dijkstra算法函数
def dijkstra(graph, start_node, end_node):
    # 初始化起点
    unvisited_nodes = [n for n in graph] # 未遍历节点列表
    shortest_distances = {n:float('inf') for n in graph} # 起点到每个节点的最短距离
    shortest_distances[start_node] = 0 # 起点到自身的距离为0
    path = {} # 每个节点的前驱节点
    current_node = start_node # 初始化当前节点

    while current_node != end_node:
        # 计算当前节点相邻节点的最短距离
        for neighbor in graph[current_node]:
            if neighbor in unvisited_nodes:
                distance = graph[current_node][neighbor]
                if distance + shortest_distances[current_node] < shortest_distances[neighbor]:
                    shortest_distances[neighbor] = distance + shortest_distances[current_node]
                    path[neighbor] = current_node

        # 标记当前节点为已遍历
        unvisited_nodes.remove(current_node)

        # 选择未遍历节点中距离起点最近的节点
        candidates = {n: shortest_distances[n] for n in unvisited_nodes}
        if not candidates:
            return "路径不存在"
        current_node = min(candidates, key=candidates.get)

    # 构造最短路径
    path_list = [end_node]
    last_node = end_node
    while last_node != start_node:
        last_node = path[last_node]
        path_list.append(last_node)
    return "->".join(path_list[::-1]), shortest_distances[end_node]

# 测试Dijkstra算法
print(dijkstra(graph, 'pidancode.com', 'github.com'))

# 定义一个字符串作为图
graph = {
    'pidancode.com': {'coding.net':1, 'github.com':2},
    'coding.net': {'pidancode.com':1, 'github.com':1},
    'github.com': {'pidancode.com':2, 'coding.net':1}
}

# 定义Floyd算法函数
def floyd(graph):
    nodes = list(graph.keys())
    n = len(nodes)
    distances = [[float('inf')]*n for _ in range(n)]

    # 初始化距离矩阵，相邻节点的距离为边权重，自身节点的距离为0
    for i in range(n):
        distances[i][i] = 0
        for j in graph[nodes[i]]:
            distances[i][nodes.index(j)] = graph[nodes[i]][j]

    # 动态规划求解最短路径
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if distances[i][j] > distances[i][k] + distances[k][j]:
                    distances[i][j] = distances[i][k] + distances[k][j]

    # 构造结果字典
    result = {nodes[i]: {nodes[j]: distances[i][j] for j in range(n)} for i in range(n)}
    return result

# 测试Floyd算法
print(floyd(graph))

import networkx as nx
import matplotlib.pyplot as plt
from networkx.drawing.nx_agraph import graphviz_layout

# 绘制图形
G = nx.DiGraph(graph)
pos = graphviz_layout(G, prog='dot')
nx.draw(G, pos, with_labels=True, font_size=14, font_family='arial')
edge_labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_size=10, font_family='arial')

# Dijkstra算法求解最短路径
path, distance = dijkstra(graph, 'pidancode.com', 'github.com')
print("最短路径为“%s”，距离为%d" % (path, distance))

# 标注最短路径
path_nodes = path.split("->")
path_edges = [(path_nodes[i], path_nodes[i+1]) for i in range(len(path_nodes)-1)]
nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color='r', width=2)

# 输出图片到文件
plt.savefig("dijkstra.png")