Dijkstra mendukung solusi dengan jumlah tepi terkecil jika beberapa jalur memiliki bobot yang sama

Anda dapat memodifikasi grafik apa pun sehingga Dijkstra's menemukan solusinya dengan jumlah tepi minimal sebagai berikut: $G$

Lipat gandakan setiap bobot tepi dengan angka $a$ , lalu tambahkan $1$ ke bobot untuk menghukum setiap tepi tambahan dalam solusi, yaitu

$w'(u,v)=a*w(u,v)+1$

Ini tidak bekerja untuk semua nilai $a$ ; $a$ perlu setidaknya $x$ agar ini berfungsi. Jika $a$ bukan angka minimum ini, itu mungkin tidak memilih jalur terpendek. Bagaimana cara menemukan nilai minimum ini $x$ ?

Ps. Ini dilakukan secara rekreasional, saya sudah selesai mengerjakan PR.

algorithms graph-theory shortest-path Kucing Unfun
sumber

Jika dua jalur memiliki bobot yang sama, jalur dengan tepi paling sedikit harus dipilih. Maaf. Saya melihat bahwa saya tidak menjelaskannya.

The Unfun Cat

Anda juga bisa melakukannya dengan menambahkan ke semua bobot tepi, di mana , m = berat tepi minimum, e = jumlah tepi di jalur terpendek (atau bahkan keseluruhan, jika Anda tidak tahu jalur terpendek panjangnya) .

ϵ

$\epsilon$

ϵ < m / e

$\epsilon < m/e$

BlueRaja - Danny Pflughoeft

Berita gembira yang menarik, terima kasih. Harus melihatnya.

The Unfun Cat

Jawaban:

Diberikan grafik , kami mendefinisikan dengan mana untuk beberapa seperti yang diusulkan dalam komentar pertanyaan. $G = (V,E,w)$ $G'=(V,E,w')$ $w'(e) = aw(e) + 1$ $a = |E| + \varepsilon$ $\varepsilon \geq 0$

Lema
Misalkan jalan di dengan biaya , yaitu . Kemudian, memiliki biayadalam , yaitu. $P$ $G$ $C$ $w(P)=C$ $P$ $aC + |P|$ $G'$ $w'(P) = aC + |P|$

Lemma mengikuti langsung dari definisi . $w'$

Panggil hasil Dijkstra pada , yang merupakan jalur terpendek di . Asumsikan bukanlah jalur terpendek dengan tepi paling sedikit (antara semua jalur terpendek) di . Ini bisa terjadi dalam satu dari dua cara. $G'$ $P$ $G'$ $P$ $G$

$P$ bukan jalur terpendek di . Lalu, ada jalur dengan . Sebagai , ini berarti juga dengan lemma with di atas. Ini bertentangan dengan yang dipilih sebagai jalur terpendek dalam . $G$
$P'$ $w(P') < w(P)$ $|P|,|P'| \leq |E| \leq a$ $w'(P') < w'(P)$ $P$ $G'$
$P$ adalah jalur terpendek tetapi ada jalur terpendek dengan tepi lebih sedikit.
Lalu, ada jalan terpendek lain - yaitu - dengan. Ini menyiratkan bahwa oleh lemma di atas, yang sekali lagi bertentangan bahwa adalah jalur terpendek dalam . $P'$ $w(P) = w(P')$ $|P'| < |P|$ $w'(P') < w'(P)$ $P$ $G'$

Karena kedua kasus telah menyebabkan kontradiksi, memang jalur terpendek dengan tepi paling sedikit dalam . $P$ $G$

Itu mencakup setengah dari proposisi. Bagaimana, yaitu dengan ? $a < |E|$ $a = |E| - \varepsilon$ $\varepsilon \in (0,|E|)$

Sebenarnya, kami juga membutuhkan atau semua beban di adalah bilangan bulat. Kalau tidak, tidak menyebabkan bobot dalam setidaknyaselain. Ini bukan pembatasan, meskipun; kita selalu dapat mengukur dengan faktor konstan sehingga semua bobot bilangan bulat, dengan asumsi kita mulai dengan bobot rasional. $a$ $G$ $w(P') < w(P)$ $G'$ $|E|$ $w$

Raphael
sumber

Saya belum dapat menemukan bukti bahwaadalah terkecil yang ini bekerja. Saya akan memikirkannya lagi.

a = | E |

$a = |E|$

a

$a$

Raphael