C#中查找出发地到目的地最少中转航线的高效实现方案咨询

你这个场景属于边权相同的最短路径搜索，优先最少中转的需求刚好匹配BFS（广度优先搜索）的遍历特性，效率远高于暴力回溯方案，实现步骤如下：

1. 预构建航线邻接表 #

先把全量Flight列表转换成以出发地为Key的邻接索引，避免每次搜索都遍历全量航班，单条航线查询效率直接降到O(1)：

// 邻接表结构：key为出发地，value为该出发地可直达的<目的地, 票价>列表
Dictionary<string, List<(string Destination, decimal Price)>> flightAdjacency = new();
foreach (var flight in flightList)
{
    if (!flightAdjacency.ContainsKey(flight.Origin))
    {
        flightAdjacency[flight.Origin] = new List<(string, decimal)>();
    }
    flightAdjacency[flight.Origin].Add((flight.Destination, flight.Price));
}

2. 优先匹配直飞航线 #

按需求优先级先校验是否存在直飞航线，存在直接返回，无需走后续搜索逻辑：

public List<Flight> SearchRoute(string origin, string destination, Dictionary<string, List<(string Destination, decimal Price)>> adjacency)
{
    // 先查直飞
    if (adjacency.TryGetValue(origin, out var directReachable))
    {
        var targetDirect = directReachable.FirstOrDefault(f => f.Destination == destination);
        if (targetDirect != default)
        {
            return new List<Flight>
            {
                new Flight { Origin = origin, Destination = destination, Price = targetDirect.Price }
            };
        }
    }

3. 无直飞时用BFS搜索最少中转航线 #

BFS是按层遍历的，第一层对应中转0次（直飞）、第二层对应中转1次、第三层对应中转2次，第一次搜索到目的地时得到的路径就是中转次数最少的路径，无需回溯所有可能路径，搜索效率高：

// BFS队列元素：当前所在城市、累计票价、已走航线路径
    Queue<(string CurrentCity, decimal TotalPrice, List<Flight> Path)> searchQueue = new();
    // 已访问城市集合，避免出现A->B->A的循环无效路径
    HashSet<string> visited = new();

    searchQueue.Enqueue((origin, 0, new List<Flight>()));
    visited.Add(origin);

    while (searchQueue.Count > 0)
    {
        var currentNode = searchQueue.Dequeue();
        // 当前城市无可用航线直接跳过
        if (!adjacency.TryGetValue(currentNode.CurrentCity, out var nextFlights)) continue;

        foreach (var nextRoute in nextFlights)
        {
            // 匹配到目的地，直接返回路径，BFS特性保证这是中转次数最少的
            if (nextRoute.Destination == destination)
            {
                var finalPath = new List<Flight>(currentNode.Path);
                finalPath.Add(new Flight
                {
                    Origin = currentNode.CurrentCity,
                    Destination = nextRoute.Destination,
                    Price = nextRoute.Price
                });
                return finalPath;
            }
            // 未访问过的城市才加入队列继续搜索
            if (!visited.Contains(nextRoute.Destination))
            {
                visited.Add(nextRoute.Destination);
                var newPath = new List<Flight>(currentNode.Path);
                newPath.Add(new Flight
                {
                    Origin = currentNode.CurrentCity,
                    Destination = nextRoute.Destination,
                    Price = nextRoute.Price
                });
                searchQueue.Enqueue((nextRoute.Destination, currentNode.TotalPrice + nextRoute.Price, newPath));
            }
        }
    }
    // 无可用航线返回空
    return null;
}

可选优化点 #

• 如果同中转次数下需要选总价最低的航线，不要找到第一个匹配目的地就返回，遍历完当前层（相同中转次数）的所有节点，对比所有匹配项的总价选最低的即可
• 航线数据量非常大的场景可以用双向BFS优化：从出发地和目的地同时启动BFS搜索，两个方向碰头时就得到最短路径，搜索范围比单向BFS小很多，效率更高

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