Cheapest Flights Within K Stops

Q: Berapa kompleksitas waktu untuk Cheapest Flights Within K Stops?

Bellman-Ford yang dibatasi hingga k+1 putaran membutuhkan waktu O(k · E) untuk E penerbangan, dan ruang tambahan O(n) untuk dua array harga. Jika suatu putaran tidak mengubah apa pun, putaran berikutnya menerima harga yang sama, sehingga kamu bisa berhenti lebih awal.

Q: Mengapa algoritma Dijkstra tidak bekerja untuk Cheapest Flights Within K Stops?

Dijkstra menyimpan satu harga terbaik untuk setiap kota dan tidak pernah mengunjungi kembali kota yang sudah ditetapkan. Di sini, rute yang lebih mahal menuju sebuah kota bisa jadi berguna jika membutuhkan lebih sedikit penerbangan. Dijkstra kembali bekerja pada state (kota, penerbangan yang digunakan), sehingga jumlah state menjadi k+1 kali lipat.

Q: Bisakah kamu menyelesaikan Cheapest Flights Within K Stops dengan BFS?

Ya. Level r memuat kota-kota yang dicapai dengan tepat r penerbangan, beserta harganya. Masukkan sebuah kota ke level berikutnya hanya jika harga barunya lebih rendah daripada harga terbaik yang pernah ditemukan untuk kota tersebut, dan berhentilah setelah k+1 level. Cara ini memberikan jawaban yang sama seperti Bellman-Ford, tetapi hanya mengikuti penerbangan dari kota-kota yang harganya berubah.

SedangJalur terpendek Graf

+10

Ada n kota yang diberi nomor dari 0 hingga n-1, serta daftar penerbangan satu arah: flights[i] = [from, to, price] adalah penerbangan dari kota from ke kota to dengan biaya price.

Kembalikan total harga terendah untuk perjalanan dari src ke dst dengan paling banyak k kali transit, yang berarti paling banyak k+1 penerbangan. Jika perjalanan seperti itu tidak ada, kembalikan -1.

Fungsi

findCheapestPrice(n: integer, flights: integer-2d-array, src: integer, dst: integer, k: integer) → integer

ninteger: jumlah kota
flightsinteger-2d-array: penerbangan satu arah, masing-masing sebagai [from, to, price]
srcinteger: kota tempat perjalanan dimulai
dstinteger: kota tempat perjalanan berakhir
kinteger: jumlah perhentian maksimum yang diizinkan antara src dan dst
Mengembalikaninteger: harga terendah untuk perjalanan dengan paling banyak k pemberhentian, atau -1

Batasan

2 ≤ n ≤ 1000
1 ≤ flights.length ≤ 4500
flights[i] = [from, to, price] dengan 0 ≤ from, to < n dan from ≠ to
1 ≤ price ≤ 10⁴
Tidak ada dua penerbangan yang memiliki from dan to yang sama.
0 ≤ src, dst < n dan src ≠ dst
0 ≤ k < n

Contoh

Input: n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 1
Output: 230
Penjelasan: Satu pemberhentian memungkinkan dua penerbangan: 0 → 1 → 3 biayanya 50 + 180 = 230 dan 0 → 2 → 3 biayanya 200 + 50 = 250. Rute yang lebih murah, 0 → 1 → 2 → 3, memiliki dua pemberhentian.

Input: n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 2
Output: 150
Penjelasan: Dua pemberhentian memungkinkan tiga penerbangan, jadi 0 → 1 → 2 → 3 sekarang diperbolehkan, dan biayanya 50 + 50 + 50 = 150.

Pertanyaan lanjutan

Bagaimana cara mengembalikan kota-kota dalam perjalanan termurah beserta harganya?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Ini adalah masalah jalur terpendek dengan batas jumlah penerbangan. Algoritma Dijkstra yang hanya menggunakan kota tidak berhasil, karena cara termurah untuk mencapai sebuah kota mungkin menghabiskan jatah perhentian yang dibutuhkan untuk sisa perjalanan. Bellman-Ford sesuai dengan batas tersebut: putaran r menemukan harga termurah dengan paling banyak r penerbangan, jadi kamu menjalankan k+1 putaran.

Coba setiap rute dengan paling banyak k+1 penerbangan

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Telusuri setiap rute dari src menggunakan stack berisi (kota, harga, jumlah penerbangan yang digunakan). Rute yang mencapai dst mencatat harganya lalu berhenti, karena setiap harga bernilai positif. Rute dengan k+1 penerbangan dibuang; rute lainnya diperpanjang dengan setiap penerbangan dari kotanya. Setiap perjalanan yang diizinkan akan dibentuk, jadi harga terbaik yang tercatat adalah harga yang tepat.

Jumlah rute bertambah seperti d pangkat k+1, dengan d penerbangan dari sebuah kota. Dengan 4 penerbangan per kota dan k = 29, jumlahnya adalah 4^30 ≈ 1.2 × 10^18 rute.

Algoritma

Kelompokkan penerbangan berdasarkan kota keberangkatan.
Push (src, 0, 0): kota, harga sejauh ini, jumlah penerbangan yang ditempuh.
Pop sebuah rute. Jika kotanya adalah dst, simpan harganya jika itu yang terbaik sejauh ini.
Jika tidak, dan rute tersebut menempuh kurang dari k+1 penerbangan, push satu rute yang lebih panjang untuk setiap penerbangan yang berangkat dari kotanya.
Saat stack kosong, kembalikan harga terbaik, atau -1 jika tidak ada yang mencapai dst.

def findCheapestPrice(n, flights, src, dst, k):
    out = [[] for _ in range(n)]
    for a, b, price in flights:
        out[a].append((b, price))
    best = -1
    # Each entry is a route in progress: (city, price so far, flights taken).
    stack = [(src, 0, 0)]
    while stack:
        city, cost, used = stack.pop()
        if city == dst:
            if best == -1 or cost < best:
                best = cost
            continue
        # k stops allow at most k+1 flights.
        if used == k + 1:
            continue
        for nxt, price in out[city]:
            stack.append((nxt, cost + price, used + 1))
    return best

Bellman-Ford dibatasi hingga k+1 putaran

Intuisi

Misalkan cost[c] adalah harga termurah untuk mencapai kota c dengan paling banyak r penerbangan. Pada r = 0, hanya src yang dapat dicapai, dengan harga 0. Perjalanan ke a dengan paling banyak r penerbangan, lalu dilanjutkan dengan penerbangan a → b, merupakan perjalanan ke b dengan paling banyak r+1 penerbangan. Jadi, setiap putaran menawarkan cost[a] + price ke b untuk setiap penerbangan. Setelah k+1 putaran, cost[dst] adalah jawabannya.

Setiap putaran membaca harga dari putaran sebelumnya dan menulis ke salinan, sehingga harga yang ditetapkan selama suatu putaran tidak dapat digunakan untuk penerbangan lain pada putaran yang sama. Pada contoh pertama dengan k = 1, harga ke kota 2 turun menjadi 100 pada putaran 2, tetapi tidak ada putaran tersisa untuk melanjutkan penerbangan ke kota 3 dengan harga 150.

Setiap putaran membaca semua penerbangan satu kali: waktu O(k · E) untuk E penerbangan, dan ruang O(n) untuk kedua array.

Algoritma

Atur cost[src] = 0 dan setiap cost lainnya menjadi tak hingga.
Ulangi k+1 kali: salin cost ke dalam next.
Untuk setiap penerbangan [a, b, price] dengan cost[a] bernilai hingga, jika cost[a] + price < next[b], atur next[b] = cost[a] + price.
Ganti cost dengan next, lalu berhenti lebih awal jika tidak ada yang berubah.
Kembalikan cost[dst], atau -1 jika nilainya masih tak hingga.

def findCheapestPrice(n, flights, src, dst, k):
    INF = float("inf")
    # cost[c]: the cheapest price to reach city c with the flights allowed so far.
    cost = [INF] * n
    cost[src] = 0
    # Each round allows one more flight; k stops means k+1 flights.
    for _ in range(k + 1):
        # Read last round's prices and write into a copy,
        # so one round can never chain two flights.
        nxt = cost[:]
        changed = False
        for a, b, price in flights:
            if cost[a] != INF and cost[a] + price < nxt[b]:
                nxt[b] = cost[a] + price
                changed = True
        cost = nxt
        if not changed:
            break
    return -1 if cost[dst] == INF else cost[dst]

Jebakan dan kasus tepi

Menghitung pemberhentian sebagai penerbangan. k pemberhentian berarti k+1 penerbangan dan k+1 putaran.
Memperbarui secara langsung. Dengan 0 → 1, 1 → 2, 2 → 3 masing-masing seharga 1, dalam urutan tersebut, ditambah 0 → 3 seharga 500 dan k = 0, satu putaran merangkai tiga penerbangan dan menghasilkan 3, bukan 500.
Menjalankan Dijkstra biasa pada kota-kota. Dengan 0 → 1 dan 1 → 2 masing-masing seharga 1, 0 → 2 seharga 40, 2 → 3 seharga 1 dan k = 1, algoritma menetapkan kota 2 pada biaya 2 setelah dua penerbangan dan melewatkan rute 0 → 2 → 3 dengan biaya 41.
Terbang dari kota yang belum dicapai. Jika infinity adalah nilai int terbesar, cost[a] + price akan melingkar menjadi negatif dalam 32 bit. Periksa terlebih dahulu apakah cost[a] bernilai terbatas.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu untuk Cheapest Flights Within K Stops?

Bellman-Ford yang dibatasi hingga k+1 putaran membutuhkan waktu O(k · E) untuk E penerbangan, dan ruang tambahan O(n) untuk dua array harga. Jika suatu putaran tidak mengubah apa pun, putaran berikutnya menerima harga yang sama, sehingga kamu bisa berhenti lebih awal.

Mengapa algoritma Dijkstra tidak bekerja untuk Cheapest Flights Within K Stops?

Dijkstra menyimpan satu harga terbaik untuk setiap kota dan tidak pernah mengunjungi kembali kota yang sudah ditetapkan. Di sini, rute yang lebih mahal menuju sebuah kota bisa jadi berguna jika membutuhkan lebih sedikit penerbangan. Dijkstra kembali bekerja pada state (kota, penerbangan yang digunakan), sehingga jumlah state menjadi k+1 kali lipat.

Bisakah kamu menyelesaikan Cheapest Flights Within K Stops dengan BFS?

Ya. Level r memuat kota-kota yang dicapai dengan tepat r penerbangan, beserta harganya. Masukkan sebuah kota ke level berikutnya hanya jika harga barunya lebih rendah daripada harga terbaik yang pernah ditemukan untuk kota tersebut, dan berhentilah setelah k+1 level. Cara ini memberikan jawaban yang sama seperti Bellman-Ford, tetapi hanya mengikuti penerbangan dari kota-kota yang harganya berubah.

def findCheapestPrice(n, flights, src, dst, k):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

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

Output yang diharapkan