如何用PHP与MySQL结合图（如Dijkstra算法）计算距离并展示快递价格？

第一步：把快递网络建模成图 #

先把你的快递网点和运输路线转换成图结构，这是实现的核心基础：

• 节点（Node）：对应各个快递网点（比如北京仓、上海分拣中心），用唯一标识（如北京、SHANGHAI）区分。
• 边（Edge）：对应两个网点之间的运输路线，边上的权重设为两地的运输距离（也可以直接用运输成本，根据需求调整）。

举个简单的代码建模示例（Python字典实现邻接表）：

# 邻接表表示：key是节点，value是{相邻节点: 距离}
graph = {
    "北京": {"天津": 137, "石家庄": 283},
    "天津": {"北京": 137, "济南": 357},
    "石家庄": {"北京": 283, "郑州": 412},
    "济南": {"天津": 357, "郑州": 390, "南京": 665},
    "郑州": {"石家庄": 412, "济南": 390, "武汉": 536},
    "南京": {"济南": 665, "上海": 301},
    "武汉": {"郑州": 536, "广州": 1069},
    "上海": {"南京": 301, "广州": 1432},
    "广州": {"武汉": 1069, "上海": 1432}
}

第二步：实现Dijkstra算法（新手友好版） #

先写最直观的版本，能跑通再考虑优化：

def dijkstra(graph, start, end):
    # 初始化：所有节点距离设为无穷大，起点距离为0
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    # 记录路径（可选，用于展示快递路线）
    paths = {node: [] for node in graph}
    paths[start] = [start]
    # 未访问节点集合
    unvisited = set(graph.keys())

    while unvisited:
        # 找到当前未访问节点中距离最小的节点
        current_node = min(unvisited, key=lambda node: distances[node])
        # 到达终点就提前退出
        if current_node == end:
            break
        # 遍历当前节点的所有邻居
        for neighbor, distance in graph[current_node].items():
            # 计算经过当前节点到邻居的距离
            new_distance = distances[current_node] + distance
            # 如果新距离更短，更新距离和路径
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                paths[neighbor] = paths[current_node] + [neighbor]
        # 标记当前节点为已访问
        unvisited.remove(current_node)
    
    return distances[end], paths[end]

测试示例：

# 计算北京到广州的最短距离和路径
distance, path = dijkstra(graph, "北京", "广州")
print(f"最短运输距离：{distance}公里")
print(f"运输路径：{' -> '.join(path)}")

输出结果：

最短运输距离：1898公里
运输路径：北京 -> 石家庄 -> 郑州 -> 武汉 -> 广州

第三步：关联快递价格 #

拿到最短距离后，就可以根据定价规则计算快递费用，比如按里程阶梯定价：

def calculate_express_price(distance, weight):
    # 示例定价规则：首重1kg内，0-500公里10元，500-1500公里15元，1500+公里20元；续重每kg加5元
    base_price = 0
    if distance <= 500:
        base_price = 10
    elif 500 < distance <= 1500:
        base_price = 15
    else:
        base_price = 20
    # 计算续重费用
    if weight > 1:
        base_price += (weight - 1) * 5
    return base_price

# 计算2kg快递的价格
price = calculate_express_price(distance, 2)
print(f"预估快递价格：{price}元")

新手实用提示 #

• 真实数据获取：实际项目中，网点间的距离可以通过地图API获取，或者使用预先整理的官方运输里程表。
• 算法优化：如果网点数量超过50个，建议用heapq模块实现优先队列优化，提升找最小距离节点的效率。
• 异常处理：要加判断逻辑，处理用户输入的起点/终点不在网点列表中的情况，避免程序报错。

内容的提问来源于stack exchange，提问作者Sifat Sakib