Flexport上海SE II面经

wing0zfz 发表于 2022-12-7 04:38
感谢楼主！想问一下路径规划这道题最短路的那一问指的是最省钱的路径吗（航班有个price？），是用的Dijkstr ...

最短路径只的是港口的数量，比如出发地是A，终止地是D，可以选择A->B->D, 也可以选择A->C->E->D, 那最终选择的是A->B->D。不过要求的是输出航班号，比如A->B的航班是“D01”，B->D的航班是"D03", 那么输出"D01、D03"。
面试官是让我自己去设计和实现需要哪些类，以及需要哪些成员，但要实现的两个函数是他说的，应该不算OOD。

可以问一下楼主之前有多少年经验吗？

charlielei 发表于 2022-12-7 07:21
可以问一下楼主之前有多少年经验吗？

1年的工作经验

Mr_fitz 发表于 2022-12-7 01:06
最短路径只的是港口的数量，比如出发地是A，终止地是D，可以选择A->B->D, 也可以选择A->C->E->D, 那最终 ...

懂了，感谢楼主！

为了实现这个功能，我们需要建立一个航班路径的数据结构，来存储所有航班路径的信息。这个数据结构可以使用图来实现，每个港口都是图的一个节点，每条航线就是图的一条边。

为了添加航班路径，可以使用以下函数：

Copy code
def add_flight_route(graph, source, destination, cost):
    if source not in graph:
        graph[source] = {}
    if destination not in graph[source]:
        graph[source][destination] = cost
    else:
        graph[source][destination] = min(graph[source][destination], cost)
这个函数接受三个参数：图、起点和终点。它会在图中添加一条从起点到终点的边，边权为 cost。如果图中已经存在这条边，则更新边权为最小值。

为了给定一个订单，返回运送这个订单的最短航线路径，可以使用以下函数：

Copy code
def find_shortest_route(graph, source, destination):
    if source not in graph or destination not in graph:
        return None
    if source == destination:
        return 0

    # 使用 Dijkstra 算法求解最短路径
    visited = {source: 0}
    pq = [(0, source)]
    while pq:
        cost, node = heappop(pq)
        if node == destination:
            return cost
        if node in visited and visited[node] < cost:
            continue
        for neighbor, c in graph[node].items():
            if neighbor not in visited or visited[neighbor] > cost + c:
                visited[neighbor] = cost + c
                heappush(pq, (cost + c, neighbor))
    return None
这个函数接受三个参数：图、起点

感谢楼主，感觉这个是新题？马住