Mengapa kita tidak dapat menemukan jalur terpendek dengan bobot negatif hanya dengan menambahkan konstanta sehingga semua bobot positif?

Saat ini saya membaca pengantar algoritma dan datang dengan algoritma Johnson yang tergantung pada memastikan bahwa semua jalur positif.

algo tergantung pada menemukan fungsi bobot baru (w ') yang positif untuk semua tepi dan menjaga kebenaran hubungan jalur terpendek.

Ia melakukannya dengan menghitung nilai h (s), h (d) yang akan ditambahkan ke nilai asli w.

Pertanyaan saya adalah, mengapa tidak hanya menemukan w terkecil dalam grafik dan menambahkannya ke semua tepi? ini akan memenuhi kedua kondisi dan akan membutuhkan lebih sedikit perhitungan.

algorithms graph-theory graphs shortest-path Mr.Me
sumber

Sudahkah Anda mencoba membuktikan klaim Anda atau menemukan contoh tandingan? Petunjuk: intuisi Anda salah. (Komunitas, saya cukup yakin ini duplikat. Bisakah Anda menemukannya?)

Raphael

@ Raphael Saya cukup yakin itu adalah penipuan juga, tapi saya pikir itu akan lebih cepat untuk menjawabnya daripada menemukan korban penipuan itu.

David Richerby

@ Raphael Saya minta maaf karena saya tidak bisa mengucapkan pertanyaan saya dalam format tertentu saya tidak bisa mencarinya.

Mr.Me

Kami memang memiliki pertanyaan yang sudah menjelaskan hal ini , tetapi sudah ditandai sebagai dup dari pertanyaan lain yang cukup membingungkan dan sulit dipahami, dan itu mencampur beberapa pertanyaan berbeda . Karena itu, saya pikir pertanyaan ini memiliki nilai lebih dari apa yang kita miliki sebelumnya. Jika Anda mau, saya kira kita bisa menargetkan ulang dups (tutup sebagai dup ini daripada apa yang mereka tunjukkan saat ini).

Jawaban:

Menambahkan bobot ke setiap sisi menambah bobot lebih untuk jalur panjang daripada jalur pendek. (Panjang dalam arti memiliki banyak sisi.)

Sebagai contoh, misalkan tepi berbiaya terendah memiliki bobot $-2$ dan ada dua jalur dari $a$ ke $b$ : satu tepi berat $3$ dan jalur dengan dua tepi, masing-masing berat $1$ . Jalur dua sisi memiliki bobot terendah. Namun, jika Anda menambahkan $2$ ke setiap tepi, jalur satu sisi memiliki bobot $5$ tetapi jalur dua sisi sekarang memiliki bobot $6$ , sehingga Anda mendapatkan jawaban yang salah.

David Richerby
sumber

Menambah setiap berat tepi dengan jumlah yang sama tidak serta merta meningkatkan setiap jalur dengan jumlah jarak yang sama. Sebaliknya, peningkatan jalur sering tidak proporsional yang tergantung pada berapa banyak tepi jalan.

Pendechosen
sumber

Efek ini sudah disebutkan dalam jawaban lain.

Yuval Filmus

Saya hanya mengulanginya sampai kebingungan.

Pendechosen