2025届美团秋招笔试题

在2025届美团的秋招笔试中，面试者通常会面临多个技术性题目，涉及数据结构与算法、系统设计、数据库、网络协议等多个方面。本文将就常见的一类题目——最短路径问题，提供详细的题目解析和代码示例。

题目背景

假设有一个由城市和道路组成的图，城市被表示为节点，道路被表示为节点之间的边。每条边都有一个非负的权重，表示从一个城市到另一个城市的距离。给定起始城市和目标城市，请找出从起始城市到目标城市的最短路径及其距离。

题目要求

1. 输入一个无向加权图，图的顶点数和边数分别为N和M。
2. 输入起始城市和目标城市。
3. 输出从起始城市到目标城市的最短路径的距离以及具体的路径。

解题思路

最短路径问题可以用Dijkstra算法解决。Dijkstra算法适合用于图中所有边权非负的情况，它的基本思想是通过维护一个最小优先队列（堆）来逐步扩展已知的最短路径。

Dijkstra算法实现

我们可以用Python实现Dijkstra算法。以下是代码示例：

import heapq

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = {i: [] for i in range(vertices)}

    def add_edge(self, u, v, weight):
        self.graph[u].append((v, weight))
        self.graph[v].append((u, weight))  # 因为是无向图

    def dijkstra(self, start, end):
        # 初始化距离和优先队列
        distances = {i: float('inf') for i in range(self.V)}
        distances[start] = 0
        priority_queue = [(0, start)]  # (距离, 点)
        prev = {i: None for i in range(self.V)}  # 用于回溯路径

        while priority_queue:
            current_distance, current_vertex = heapq.heappop(priority_queue)

            if current_distance > distances[current_vertex]:
                continue

            for neighbor, weight in self.graph[current_vertex]:
                distance = current_distance + weight

                # 只有在找到更短的路径时才更新时间和前驱
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    prev[neighbor] = current_vertex
                    heapq.heappush(priority_queue, (distance, neighbor))

        return distances, prev

    def shortest_path(self, start, end):
        distances, prev = self.dijkstra(start, end)

        # 回溯路径
        path = []
        while end is not None:
            path.append(end)
            end = prev[end]
        path.reverse()  # 反转路径

        return distances[path[0]], path  # 返回距离和路径

# 测试代码
if __name__ == "__main__":
    g = Graph(6)
    g.add_edge(0, 1, 7)
    g.add_edge(0, 2, 9)
    g.add_edge(0, 5, 14)
    g.add_edge(1, 2, 10)
    g.add_edge(1, 3, 15)
    g.add_edge(2, 3, 11)
    g.add_edge(2, 5, 2)
    g.add_edge(3, 4, 6)
    g.add_edge(4, 5, 9)

    start = 0
    end = 4
    distance, path = g.shortest_path(start, end)
    print(f"从城市 {start} 到城市 {end} 的最短距离是 {distance}，路径为 {path}")

结论

通过上述代码，你可以在给定的无向加权图中计算出从起始城市到目标城市的最短路径及其距离。Dijkstra算法不仅高效，而且易于实现，是处理类似问题的常用算法之一。在美团的笔试中，这样的题目能够有效地考察候选人的编程能力和对算法的理解。同时，面试者在解答时还需要考虑测试边界情况以及算法的时间复杂度分析，以保证解答的完整性和准确性。