説明:

これはLeetCodeのCheapest Flights Within K Stops題です.
従来の多出口問題とほぼ同様であるが,方向性重み付け図で示す航路では,乗り換え後の目的地までの最短距離を計算する問題である.
一般的なマルチアウトレット問題とは少し異なり,乗り換えで移動できるノード数が限られている.
例えば、上記の航路がある場合、0番空港で一度も乗り換えずに2番空港に着く最短距離はいくらですか?この場合、0番空港から2番空港までの500本の経路しか利用できません.
1回の乗り換えが許可されている場合は、0番、1番、2番の空港順に移動し、100+100の経路を利用することができます.

に答える

Dijkstra#1(失敗)

最初の試みの解は、以下の変形によって複数のアルゴリズムを実現した.

料金、ノード、乗り継ぎで使用される空港数を優先順位キューに挿入します.

これまで訪問した空港数が乗り換え制限を超えていれば探索は行われなかった.

の現在までの累積コストが既存の計算コストよりも大きい場合は、探索は行われない.

特に,最後の条件は最適化のために加えられたものと考えられるが,これは以下の反例によって阻止される.
上のグラフでは、0番空港から3番空港まで1回しか乗り換えられない場合、最適な経路は5+1=6です.1番空港を経由すると1+1+1=3の方が効率的ですが、1回の乗り換えの制限しかないので2番空港に戻るしかありません.
しかし,「累積費用が既存の計算費用より大きい場合は探索を行わない」という条件が問題となっている.マルチアウトレットアルゴリズムで検索する場合、0番空港から1番空港までの経路料金が最も低いので、まず1番空港を検索してから2番空港を検索します.また、3番空港までは乗り換え制限で探索できなかったため、0番空港から2番空港までの最短距離は1+1=2と確定した.
また、残りの料金が5の0番空港から2番空港までの経路をキューで検索すると、上記の料金2よりも現在の経路が非効率になるため、検索は行われません.ここまでが一般的なダエストラ問題なら、それが正しい方法です.
しかし、この問題には乗り換え制限があることを考慮しなければならない.0番空港から1番空港までのルートは、2番空港までは料金2で移動できますが、3番空港までは移動できません.問題はどうしても3番空港まで移動しなければならないので、この経路は実際には無駄です.
これを実現するコードは次のとおりです.

import collections
import heapq


class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
        # 노드 간 연결관계, 가중치, 초기 노드에서 다른 노드까지의 거리.
        graph = collections.defaultdict(list)
        costs = [[10001]*(n+1) for _ in range(n+1)]
        terminalCosts = [1000001]*(n+1)
        
        # 그래프 초기화
        for flight in flights:
            departure, destination, cost = flight
            graph[departure].append(destination)
            costs[departure][destination] = cost
         
        # 우선순위 큐에 (비용, 노드, 환승 횟수) 튜플 삽입. 
        queue = [(0, src, 0)]
        
        while queue:
            # 가장 적은 비용의 노드 추출.
            cost, node, stop = heapq.heappop(queue)
            # 환승 횟수를 초과했거나 기존보다 효율적이지 않은 경로 무시.
            if stop > K+1 or terminalCosts[node] <= cost:
                continue
            
            # 현재 노드의 이웃 노드를 큐에 삽입.
            for neighbor in graph[node]:
                heapq.heappush(queue, (cost + costs[node][neighbor], neighbor, stop+1))
            
            # 현재 노드까지의 이동 거리 갱신.
            terminalCosts[node] = min(cost, terminalCosts[node])
        
        # 목적지 노드까지 경로가 파악됐다면 거리값 반환.
        return -1 if terminalCosts[dst] > 1000000 else terminalCosts[dst]

Dijkstra #2(96 ms)

では、どうすれば上記の問題を解決できますか?答えは移動距離ではなく、乗り換え回数で探索を中断したかどうかを確認します.上記のグラフでは、0番空港から2番空港までの場合、料金(5>1+1)ではなく乗り換え回数(1<2)で比較すれば、有効な経路に沿って最短距離を探索することができます.
しかし,実装するだけではタイムアウトが発生し,アルゴリズムの限界か実装の誤りかを特定できない.逆に、現在のナビゲーションノードが最短距離を有するマルチタスクルーティングアルゴリズムの特性により、ナビゲーション中に宛先ノードに到達したときに直ちにナビゲーションを終了し、不要な演算を無視することができる.

import collections
import heapq


class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
        # 노드 간 연결관계, 가중치, 시작 노드와 다른 노드간 거리.
        graph = collections.defaultdict(list)
        costs = [[10001]*(n) for _ in range(n)]
        terminalCosts = [1000001]*(n)
        
        # 그래프 초기화.
        for flight in flights:
            departure, destination, cost = flight
            graph[departure].append(destination)
            costs[departure][destination] = cost
        
        # src 노드부터 탐색 시작.
        queue = [(0, src, 0)]
        
        while queue:
            # 제일 낮은 비용의 경로부터 탐색.
            cost, node, stop = heapq.heappop(queue)
            # 현재 방문한 노드의 거리값 갱신.
            terminalCosts[node] = min(cost, terminalCosts[node])

            # 문제에서 요구한 환승 횟수를 초과하게 되는 경우 탐색 종료.
            if stop > K:
                continue
                
            # 현재 노드가 목적지 노드라면 탐색 종료.
            if node == dst:
                return terminalCosts[node]
            
            # 현재 노드의 이웃 노드를 증가된 환승 횟수와 함께 탐색 대기열에 추가.
            for neighbor in graph[node]:
                calculatedCost = cost + costs[node][neighbor]
                heapq.heappush(queue, (calculatedCost, neighbor, stop+1))

        # 목적지 노드까지 도달할 수 있다면 최단거리 반환.
        return -1 if terminalCosts[dst] > 1000000 else terminalCosts[dst]

しかし,この問題のもう一つの特徴は,最短距離を要求する経路(開始ノード,到達ノード)を明確に指定することである.この場合、ターミナルCostsアレイのように、開始ノードから他のすべてのノードまでの長さを格納する必要はありません.上のコードをもう少し簡略化して、以下に示します.

import collections
import heapq


class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
        # 노드 간 연결관계, 가중치.
        graph = collections.defaultdict(list)
        costs = [[10001]*(n) for _ in range(n)]
        
        # 그래프 초기화.
        for flight in flights:
            departure, destination, cost = flight
            graph[departure].append(destination)
            costs[departure][destination] = cost
        
        # src 노드부터 탐색 시작.
        queue = [(0, src, 0)]
        
        while queue:
            # 제일 적은 비용의 탐색 경로 추출.
            cost, node, stop = heapq.heappop(queue)

            # 현재 경로가 목적지 노드라면 최단거리 반환. 
            if node == dst:
                return cost
            
            # 환승 횟수를 초과하게 된다면 더이상 탐색하지 않음.
            if stop > K:
                continue
            
            # 현재 노드의 이웃 노드를 탐색 큐에 삽입.
            for neighbor in graph[node]:
                calculatedCost = cost + costs[node][neighbor]
                heapq.heappush(queue, (calculatedCost, neighbor, stop+1))
                
        # 목적지 노드의 최단거리를 발견하지 못했다면 -1 반환.    
        return -1

時間の差は大きくありませんが、不要な変数はないと思います.これはより簡潔でより良いコードです.

ポスト

乗り換え回数で決まる部分を実現したが,タイムアウト問題で苦戦し,現在の経路が目的地ノードであればすぐに戻る論理を実現したので,解答が得られる.最短経路というマルチアウトプットアルゴリズムの核心原理を知れば,この点が考えられるはずである.昨日はあんなに勉強したのに、明らかに足りないと感じました.