Bisakah kita menemukan k jalur terpendek antara semua pasangan lebih cepat daripada menyelesaikan masalah berpasangan berulang kali?

9

Saya ingin menghasilkan jalur terpendek ( akan kurang dari 10) antara semua pasangan dalam grafik. Grafiknya adalah (sebenarnya peta kereta bawah tanah):kk

  • tertimbang positif
  • tidak diarahkan
  • jarang
  • dengan sekitar 100 node

Rencana saya saat ini adalah untuk menerapkan rute jalur terpendek ke setiap pasangan; Saya sekarang mencari alternatif yang lebih efisien (mungkin dengan pemrograman dinamis).k

algorithms graphs optimization shortest-path Franklin Yu
sumber
3
Jujur, untuk 100 simpul, sepertinya tidak mungkin Anda membutuhkan sesuatu yang lebih efisien daripada menyelesaikan masing-masing dari 45.000 masalah berpasangan.
David Richerby

Jawaban:

6

Pertama-tama, perbedaan penting dalam menghitung jalur pendek adalah apakah jalurnya harus sederhana atau tidak. Path disebut simple , jika tidak mengandung node berulang kali. Jalur dengan loop, misalnya, tidak sederhana. Perhatikan bahwa pada halaman Wikipedia yang Anda tautkan, artikel-artikel tersebut berkaitan dengan jalur yang tidak harus sederhana. Kasus jalur sederhana tampaknya lebih sulit daripada kasus dengan jalur tidak selalu sederhana.k

Masalah all-pairs -pendek jalur sederhanak

Ini tampaknya merupakan bidang penelitian yang cukup muda. Sebuah makalah terbaru oleh Agarwal dan Ramachandran dapat ditemukan di ArXiv [1]. Bagian pekerjaan sebelumnya juga akan memberi Anda beberapa wawasan tentang sejarah masalah.

Masalah semua-pasangan jalur terpendekk

Di sini, memang, itu adalah pilihan terbaik untuk hanya berulang kali menerapkan algoritma Eppstein [2]. Pengamatan umum bahwa aplikasi berulang algoritma untuk versi sumber tunggal dari masalah adalah pendekatan tercepat sudah dibuat pada tahun 1977 oleh EL Lawler [3]; Eppstein menyediakan algoritma tercepat hingga saat ini untuk submasalah ini.

Referensi

[1] Agarwal, U. dan Ramachandran, V. Menemukan Jalur dan Siklus Terpendek yang Sederhana. arXiv: 1512.02157 [cs.DS] https://arxiv.org/pdf/1512.02157.pdfk

[2] Eppstein, D. Menemukan k jalur terpendek. Jurnal SIAM tentang Komputasi 28, 2 (1999), 652-673.

[3] Lawler, EL Mengomentari penghitungan k jalur terpendek dalam grafik. Komunikasi ACM, 20 (8): 603–605, 1977.

Bikinan
sumber
Terima kasih. Karena saya bekerja dengan peta kereta bawah tanah, saya membutuhkannya untuk menjadi jalur yang sederhana (tidak masuk akal bagi perangkat lunak saya untuk memandu orang bolak-balik), jadi saya kira saya hanya akan pergi dengan algoritma Yan .
Franklin Yu
Menarik dan cukup mengejutkan bahwa ternyata 10.000 kasus masalah tidak dapat diselesaikan lebih cepat daripada hanya menyelesaikan 10.000 kasus tunggal, satu demi satu.
gnasher729
gagasan jalur dengan loop yang termasuk dalam "jalur terpendek" tampaknya berlawanan dengan intuisi & tidak biasa karena tampaknya ada "jalur" yang setara dengan loop yang dilepaskan, dan orang juga bertanya-tanya apakah jalur ini dapat dibangun secara efisien dari jalur sederhana dll ...
vzn