Apakah ada algoritma optimal untuk menemukan jalur terpendek terpanjang dalam jaringan?

13

Saya memiliki satu set besar jaringan linear dan saya ingin menemukan dua ujung dari masing-masing jaringan yang paling jauh satu sama lain di sepanjang jaringan (pada gambar di bawah, itu akan menjadi D ke K). Solusi brute force untuk masalah ini adalah menghitung jalur terpendek di sepanjang jaringan untuk setiap pasangan asal, tetapi saya memiliki ratusan jaringan dengan ribuan ujung, sehingga menghitung setiap jalur yang mungkin cukup berat.

Apakah ada cara optimal untuk menghitung ini tanpa menggunakan brute force? Bisakah saya mengecualikan beberapa poin berdasarkan beberapa aturan pintar?

Bagaimana cara menemukan jalur merah secara efisien?

EDIT: Saya telah menambahkan ilustrasi jalur terpanjang yang disebutkan oleh @Alex Tereshenkov untuk memperjelas pertanyaan saya. Jalur hitam adalah hasil dari algoritma jalur terpanjang (jalur terpanjang tanpa mengulangi semua simpul). Dalam kasus saya, bayangkan Anda memasuki jaringan dari salah satu surat dan Anda harus pergi ke surat lain secepat mungkin. Dua surat mana yang paling sulit untuk diikuti? masukkan deskripsi gambar di sini

radouxju
sumber
skill cat gila!
Adam

Jawaban:

6

Saya pikir Anda mungkin mencari Diameter Grafik jaringan Anda. Ada beberapa pertanyaan tentang stackexchange yang menyebutkan topik ini, misalnya:

Sebagian besar algoritma menyarankan untuk menghitung "all-pair shortest paths" terlebih dahulu dan memilih yang terpanjang dari itu, tetapi saya menemukan posting blog oleh Koushik Narayanan yang menyarankan pendekatan alternatif yang mungkin lebih optimal (saya tidak memeriksa), yang beralih ke setiap simpul dan menemukan pasangannya yang paling jauh:

Kita dapat menghitung lintasan dari vertex V1 sedemikian sehingga lintasan terpendek antara V1 dan salah satu verteks dan lebih panjang dari lintasan terpendek di antara verteks lain. Lihat posting ini untuk algoritme. Kemudian, kita dapat beralih melalui setiap simpul dan menemukan jalur terpanjang dengan setiap simpul sebagai root. Setelah kami memiliki daftar semua jalur terpendek terpanjang, kami dapat menemukan yang memiliki nilai maksimum dan mengembalikannya.

mkadunc
sumber
terima kasih, diameter grafik adalah persis apa yang saya cari, dan heuristik pseudo-diamter bekerja dalam kasus saya. Saya baru saja belajar kata-kata baru di sana!
radouxju
7

Menurut halaman Wikipedia masalah jalan terpanjang , masalah ini

... adalah NP-hard, artinya tidak dapat diselesaikan dalam waktu polinomial untuk grafik arbitrer kecuali P = NP. Hasil kekerasan yang lebih kuat juga diketahui menunjukkan bahwa sulit untuk diperkirakan. Namun, ia memiliki solusi waktu linier untuk grafik asiklik terarah, yang memiliki aplikasi penting dalam menemukan jalur kritis dalam masalah penjadwalan.

Jika Anda bekerja dengan (atau dapat mewakili grafik Anda sebagai DAG ), maka networkxpaket Python akan membiarkan Anda menghitungnya. Cari fungsinya dag_longest_path.

Kecuali jika saya kehilangan sesuatu, Anda harus menghitung panjang antara node grafik dan mengurutkannya yang, sayangnya, hanya akan bekerja dalam waktu linier , yaitu tidak ada algoritma yang efisien untuk ini.

Alex Tereshenkov
sumber
terima kasih atas jawabannya, sudah +1 karena informasinya. Namun, saya mencari JALUR PENDEK TERTINGGI dalam jaringan (dalam contoh saya, tidak ada jalan memutar menuju B atau H). Oleh karena itu solusi Anda tidak persis apa yang saya cari, bahkan jika itu mengisyaratkan bahwa "kekuatan kasar" mungkin satu-satunya solusi.
radouxju
@radouxju, saya mengerti. Baiklah, mari kita lihat apakah gen akan memperhatikan hal ini, dia memiliki banyak pengalaman dengan grafik, mungkin dia memiliki beberapa ide cemerlang.
Alex Tereshenkov