使用最短路径算法推荐春运回家路线

原创

查拉图斯特拉说

修改于 2024-03-19 19:51:53

1260

修改于 2024-03-19 19:51:53

文章被收录于专栏：后端架构后端架构

前言

有个博主提出想使用python分析2024春运最忙路线，然后避开热门线路，分段购票回老家。因为铁路的售票系统估计也是以利益最大化的原则售卖数量很多的热门长线线路，目前有如下几个思路：

导出所有往年的预售数据
对数据进行清洗，整理成合适的加权平均站点数据
使用最短路径算法进行计算

铁路图

本来想通过选择站点查看对应的站点数据没想到，接口都没有，只调用了一个queryCC接口

数据准备

下载 2024 年春运火车票预售数据。数据可以从 12306 网站或其他公开数据平台获取。（目前我无法获取）
数据清洗。将数据整理成统一格式，并去除缺失值和异常值。
存入stations.csv表格进行统计
以出发点为起点，对不同的站点进行客运量、时间、票价、距离加权平均，得到一个均值。

分析方法

使用 Python 的 Pandas 库进行数据分析。
计算每个站点的客运量，并根据票价、距离进行加权计算
绘制加权站点分布图，并使用最短路径算法进行计算统计。

示例代码

import pandas as pd

# 读取 CSV 文件
data = pd.read_csv("stations.csv")

# 计算每个站点的客运量、票价、距离
data["passenger_traffic"] = data["seat_count"] * data["occupancy_rate"]
data["distance"] = data["longitude"] ** 2 + data["latitude"] ** 2

# 计算每个站点的加权平均值
data["weighted_average"] = (data["passenger_traffic"] * data["price"] + data["distance"]) / 2

# 计算两点之间的最合适路线
def find_best_route(start_station, end_station):
    # 找到起点和终点的加权平均值
    start_value = data[data["station_name"] == start_station]["weighted_average"].values[0]
    end_value = data[data["station_name"] == end_station]["weighted_average"].values[0]

    # 计算所有路线的加权平均值
    routes = []
    for i in range(len(data)):
        for j in range(i + 1, len(data)):
            routes.append((data["station_name"].iloc[i], data["station_name"].iloc[j], (start_value - data["weighted_average"].iloc[i]) ** 2 + (end_value - data["weighted_average"].iloc[j]) ** 2))

    # 选择加权平均值最小的路线
    best_route = min(routes, key=lambda x: x[2])

    return best_route

# 示例
start_station = "北京站"
end_station = "上海站"

best_route = find_best_route(start_station, end_station)

print("最合适路线：", best_route)

上面直接使用暴力搜索算法，最简单直接计算最短路线，当然你可以替换成如下的一些推荐算法，我这是一种简单、直接的算法，它枚举所有可能的路径，并选择最短的路径。对于规模较小的图，是一种有效的方法。

最短路径算法

最短路径算法是图论中一个经典问题，旨在寻找图中两点之间的最短路径。最短路径算法有很多种，每种算法都有其优缺点，你可以根据需要进行选择。

常见的最短路径算法包括：

Dijkstra 算法： Dijkstra 算法是单源最短路径问题的经典算法，用于计算一个节点到其他所有节点的最短路径。该算法的时间复杂度为 O(E log V)，其中 V 是图中节点的个数，E 是图中边的个数。

算法示例：

def dijkstra(graph, start_node):
  """
  Dijkstra 算法

  Args:
    graph: 图的邻接矩阵
    start_node: 起始节点

  Returns:
    distance: 从起始节点到其他所有节点的最短路径距离
  """

  # 初始化
  distance = {}
  for node in graph:
    distance[node] = float("inf")
  distance[start_node] = 0

  # 未访问节点集合
  unvisited = set(graph.keys())

  # 循环访问所有节点
  while unvisited:
    # 找到距离最小的节点
    min_node = min(unvisited, key=lambda node: distance[node])

    # 将该节点标记为已访问
    unvisited.remove(min_node)

    # 更新相邻节点的距离
    for neighbor, weight in graph[min_node].items():
      if neighbor in unvisited:
        distance[neighbor] = min(distance[neighbor], distance[min_node] + weight)

  return distance


graph = {
  "A": {"B": 10, "C": 5},
  "B": {"A": 10, "C": 15, "D": 20},
  "C": {"A": 5, "B": 15, "D": 10},
  "D": {"B": 20, "C": 10}
}

start_node = "A"

distance = dijkstra(graph, start_node)

print(distance)

结果

Floyd-Warshall 算法： Floyd-Warshall 算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。该算法的时间复杂度为 O(V^3)。

Bellman-Ford 算法： Bellman-Ford 算法是单源最短路径问题的另一种算法，可以处理负权边，但不能处理负权环。该算法的时间复杂度为 O(VE)。

SPFA 算法： SPFA 算法是 Bellman-Ford 算法的改进版本，可以处理负权边，也能处理负权环。该算法的时间复杂度为 O(VE)。
A 算法：A 算法是一种启发式搜索算法，用于在有估价函数的情况下寻找最短路径。该算法的时间复杂度取决于估价函数的质量。

总结

在我们的日常生活中，无论是购买商品还是在社交媒体上与朋友互动，算法都在其中发挥着重要作用。许多人每天都会使用搜索引擎来获取所需的信息，并通过智能手机上的应用程序完成各种任务。同时，由于算法可以不断优化用户体验，使其更高效和便捷，因此算法在各行各业的应用也越来越广泛，成为了企业降本增效的重要手段。因此，我们可以看到，人总是在降本增效的路上越走越远，而算法技术也为我们的生活和工作带来了许多便利和机遇。