ベルマン・フォード法で乗り継ぎ k 回までのいちばん安い運賃を求める

最短経路 (BFS)問題 121

都市を結ぶ便の運賃の並びから、乗り継ぎを k 回までに抑えて出発地から目的地へ行く、いちばん安い運賃を求めます。使う便の数を 1 本ずつ増やしながら運賃を緩めていく、回数に上限のある最短経路の練習です。

海外で定番の問題リスト 4 本には入っていません

問題

n か所の都市があり、0 から n - 1 の番号が付いています。便の並び flights を受け取ります。flights[i] = [a, b, p] は、都市 a から都市 b へ運賃 p で飛ぶ片道の便です。

都市 src から都市 dst へ、乗り継ぎを k 回まで (つまり便を k + 1 本まで) 使って行くとき、運賃の合計のいちばん安い値を返す関数を書いてください。行けないなら -1 を返します。

n は 2 以上 100 以下、運賃 p は 1 以上 10000 以下の整数です
同じ a から同じ b への便は 2 本ありません。自分の都市へ戻る便もありません
src と dst は違う都市です。k は 0 以上、n より小さい整数です

入力と出力の例

例 1

0 から 3 へは、直行便 700、1 で乗り継ぐ 100 + 200 = 300、1 と 2 で乗り継ぐ 100 + 50 + 100 = 250 の道があります。乗り継ぎ 1 回までなので、2 回乗り継ぐ 250 は使えず、300 です。

flights = [[0, 1, 100], [1, 2, 50], [2, 3, 100], [1, 3, 200], [0, 3, 700]] n = 4 src = 0 dst = 3 k = 1

300

例 2

例 1 と同じ便で、乗り継ぎ 2 回までなら 250 です。

flights = [[0, 1, 100], [1, 2, 50], [2, 3, 100], [1, 3, 200], [0, 3, 700]] n = 4 src = 0 dst = 3 k = 2

250

例 3

0 から 2 へは 1 で乗り継ぐしかありませんが、乗り継ぎは 0 回までです。

flights = [[0, 1, 10], [1, 2, 10]] n = 3 src = 0 dst = 2 k = 0

-1

面接での聞かれ方

面接では、短く次のように渡されることが多いです。

「都市と便の運賃が渡されます。乗り継ぎ k 回以内で src から dst へ行くいちばん安い運賃を返してください」
ダイクストラ法で書くと「乗り継ぎの上限があるとき、いちばん安い所から確定してよいですか？」と聞かれます
「計算量は？便の数と k のどちらで決まりますか？」と聞かれます

乗り継ぎの数え方 (k 回の乗り継ぎは便 k + 1 本) を最初に確かめておくと、繰り返しの回数を 1 回ずらす間違いを防げます。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「グラフ探索と幅優先探索」に、この型の要点を表とコードでまとめています。

グラフ探索は、つながりを近い順か奥からたどります。迷路、最短の手数、講座を受ける順のような問題が同じ形です。

まず考える手順

段 1

ふつうのダイクストラ法は、いちばん安い所から確定します。けれどもこの問題では、安いけれど乗り継ぎの多い道で確定してしまうと、あとで乗り継ぎの少ない道を使いたいときに戻れません。例 1 で 2 を 150 で確定すると、3 へは乗り継ぎ 2 回の道しか見なくなります。

段 2

「便を i 本まで使ったときの、各都市へのいちばん安い運賃」を表にします。便 0 本なら src だけが 0 で、ほかは届きません。便を 1 本増やすときは、全部の便 [a, b, p] について、「a まで i 本で来る運賃 + p」が b の値より安ければ書き換えます。これを k + 1 回繰り返すと、便 k + 1 本までの答えになります。これがベルマン・フォード法を回数で止めた形です。

段 3

1 回の中で書き換えるのは、前の回の表を写した新しい表です。同じ表をその場で書き換えると、1 回の中で 0 から 1、1 から 2 と続けて進み、便を 2 本使った運賃が 1 本の回に混ざります。読むのは前の回の表、書くのは新しい表、と分けます。

段 4

k + 1 回の繰り返しのあと、dst の値が「届かない」のままなら -1、そうでなければその値が答えです。

解答

Python

def cheapest_fare(
    flights, n, src, dst, k
):
    inf = float("inf")
    cost = [inf] * n
    cost[src] = 0
    for _ in range(k + 1):
        nxt = cost[:]
        for a, b, p in flights:
            c = cost[a] + p
            if c < nxt[b]:
                nxt[b] = c
        cost = nxt
    if cost[dst] == inf:
        return -1
    return cost[dst]

JavaScript

function cheapestFare(
  flights, n, src, dst, k,
) {
  let cost = Array(n)
    .fill(Infinity);
  cost[src] = 0;
  for (let i = 0; i <= k; i++) {
    const next = [...cost];
    for (const f of flights) {
      const [a, b, p] = f;
      const c = cost[a] + p;
      if (c < next[b]) {
        next[b] = c;
      }
    }
    cost = next;
  }
  if (cost[dst] === Infinity) {
    return -1;
  }
  return cost[dst];
}

Go

func cheapestFare(
	flights [][]int,
	n, src, dst, k int,
) int {
	// 届かない印。運賃の合計より大きい
	const inf = 1 << 60
	cost := make([]int, n)
	for i := range cost {
		cost[i] = inf
	}
	cost[src] = 0
	for i := 0; i <= k; i++ {
		next := append(
			[]int{}, cost...)
		for _, f := range flights {
			a, b := f[0], f[1]
			if cost[a] == inf {
				continue
			}
			c := cost[a] + f[2]
			if c < next[b] {
				next[b] = c
			}
		}
		cost = next
	}
	if cost[dst] == inf {
		return -1
	}
	return cost[dst]
}

Python と JavaScript は、届かない印に無限大を使っています。無限大に運賃を足しても無限大なので、届いていない都市からは書き換えが起きません。Go の整数には無限大が無いので、大きな数を印にし、その都市からの便を飛ばしています。

計算量

時間は O(k × E) です。E は便の数です。k + 1 回の繰り返しで、毎回全部の便を見ます。表を写すのに毎回 O(n) かかりますが、合わせても O(k × (n + E)) です
使う記憶は O(n) です。前の回と新しい回の 2 つの表です

よくある間違い

表をその場で書き換える。 1 回の中で便を何本も進めてしまい、乗り継ぎの上限を超えた運賃が出ます。例 1 の便の順でその場で書き換えると、1 回目のうちに 0 から 1、2、3 と進み、k = 0 でも 250 になります
繰り返しを k 回にする。乗り継ぎ k 回は便 k + 1 本です。k 回で止めると、例 1 で 1 回乗り継ぐ道を見ずに、直行便の 700 を返します
ふつうのダイクストラ法で、都市ごとに 1 回だけ確定する。安くて乗り継ぎの多い道で確定すると、乗り継ぎの少ない道を見なくなり、行けるのに -1 を返すことがあります
Go で印の大きな数に運賃を足す。印から書き換えが起きないよう、届いていない都市からの便は飛ばします

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def cheapest_fare(flights: list[list[int]], n: int, src: int, dst: int, k: int) -> int:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(cheapest_fare([[0, 1, 100], [1, 2, 50], [2, 3, 100], [1, 3, 200], [0, 3, 700]], 4, 0, 3, 1))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します