Kompleksitas waktu dalam menemukan diameter grafik

Berapa kompleksitas waktu untuk menemukan diameter grafik ?$G=(V,E)$

• ${O}(|V|^2)$
• ${O}(|V|^2+|V| \cdot |E|)$
• ${O}(|V|^2\cdot |E|)$
• ${O}(|V|\cdot |E|^2)$

Diameter grafik adalah maksimum himpunan jarak jalur terpendek antara semua pasangan simpul dalam grafik.$G$

Saya tidak tahu harus berbuat apa, saya perlu analisis lengkap tentang bagaimana menyelesaikan masalah seperti ini.

Memperbarui:

Solusi ini tidak benar.

Solusinya sayangnya hanya benar (dan langsung) untuk pohon! Menemukan diameter pohon bahkan tidak memerlukan ini. Berikut adalah contoh tandingan untuk grafik (diameter 4, algoritma mengembalikan 3 jika Anda memilih ini ):$v$

Jika grafik diarahkan ini agak rumit, berikut adalah beberapa kertas yang mengklaim hasil lebih cepat dalam kasus padat daripada menggunakan algoritma untuk semua-pasangan jalur terpendek.

Namun poin utama saya adalah tentang kasus grafik tidak terarah dan dengan bobot non-negatif, saya mendengar trik yang bagus beberapa kali:

1. Pilih titik$v$
2. Temukan sedemikian rupa sehingga maksimumd ( v , kamu $u$$d(v,u)$
3. Temukan sehingga maksimumd ( u , w $w$$d(u,w)$
4. Return$d(u,w)$

Kompleksitasnya sama dengan dua pencarian pertama kali berturut-turut¹, yaitu jika grafik terhubung².$O(|E|)$

Tampaknya itu cerita rakyat, tetapi saat ini, saya masih berjuang untuk mendapatkan referensi atau untuk membuktikan koreksinya. Saya akan memperbarui ketika saya akan mencapai salah satu dari tujuan ini. Sepertinya sangat sederhana saya memposting jawaban saya sekarang, mungkin seseorang akan mendapatkannya lebih cepat.

¹ jika grafik ditimbang, wikipedia tampaknya mengatakan tetapi saya hanya yakin tentang .O ( | E | log | V |$O(|E|+|V|\log|V|)$$O(|E|\log|V|)$

² Jika grafik tidak terhubung Anda mendapatkan tetapi Anda mungkin harus menambahkan untuk memilih satu elemen dari setiap komponen yang terhubung. Saya tidak yakin apakah ini perlu dan bagaimanapun, Anda dapat memutuskan bahwa diameternya tidak terbatas dalam kasus ini.O ( α ($O(|V|+|E|)$$O(α(|V|))$

Saya berasumsi Anda berarti diameter dari yang merupakan terpanjang jalur terpendek yang ditemukan di .$G$$G$

Menemukan diameter dapat dilakukan dengan menemukan semua pasangan jalur terpendek terlebih dahulu dan menentukan panjang maksimum yang ditemukan. Algoritma Floyd-Warshall melakukan ini dalam waktu . Algoritma Johnson dapat diimplementasikan untuk mencapai waktu .O ( | V | 2 log | V | + | V | ⋅ | E |$\Theta(|V|^3)$$\cal{O}(|V|^2\log |V| + |V|\cdot|E|)$

Batas runtime kasus terburuk yang lebih kecil tampaknya sulit untuk dicapai karena ada jarak untuk mempertimbangkan dan menghitung jarak tersebut dalam waktu sublinear (diamortisasi) yang masing-masing akan menjadi sulit; lihat di sini untuk terikat terkait. Perhatikan makalah ini yang menggunakan pendekatan yang berbeda dan mendapatkan algoritma (sedikit) lebih cepat.$\cal{O}(|V|^2)$

Anda juga dapat mempertimbangkan pendekatan teori grafik aljabar. Diameter adalah bilangan bulat paling tidak dengan matriks memiliki properti bahwa semua entri bukan nol. Anda dapat menemukan dengan iterasi dari perkalian matriks. Algoritma diameter kemudian membutuhkan waktu , di mana adalah terikat untuk perkalian matriks. Misalnya, dengan generalisasi algoritma Coppersmith-Winograd oleh Vassilevska Williams, algoritma diameter akan berjalan dalam . Untuk pengantar cepat, lihat Bab 3 dalam buku Fan Chung di sini .t M = I + A M t t O ( log n ) O ( M ( n ) log n ) M ( n ) O ( n 2,3727 log n $\text{diam}(G)$$t$$M=I+A$$M^t$$t$$O(\log n)$$O(M(n) \log n)$$M(n)$$O(n^{2.3727} \log n)$

Jika Anda membatasi perhatian Anda pada kelas grafik yang sesuai, Anda dapat menyelesaikan masalah APSP dalam waktu optimal . Kelas-kelas ini termasuk setidaknya grafik interval, grafik busur lingkaran, grafik permutasi, grafik permutasi bipartit, grafik chordal kuat, grafik bipartit chordal, grafik herediter jarak, dan grafik chordal ganda. Sebagai contoh, lihat Dragan, FF (2005). Memperkirakan semua pasangan jalur terpendek dalam keluarga grafik terbatas: pendekatan terpadu. Jurnal Algoritma, 57 (1), 1-21 dan referensi di dalamnya.$O(n^2)$

Asumsi:
1. Grafik tidak berbobot
2. Grafik diarahkan

O (| V || E |) kompleksitas waktu.

Algoritma:

ComputeDiameter(G(V,E)):
  if ( isCycle( G(v,E) ) ) then
     return INFINITY
  if ( not isConnected( G(V,E) )) then
     return INFINITY
  diameter = 0
  for each vertex u in G(V,E):
     temp = BFS(G,u)
     diameter = max( temp , diameter )
  return diameter

Penjelasan:
Kami memeriksa siklus. jika grafik mengandung siklus maka kita tetap bergerak dalam loop, jadi kita akan memiliki jarak tak terbatas. Kami memeriksa terhubung. Jika grafik tidak terhubung, itu berarti simpul u dari G1 ke simpul v di G2. Di mana G1 dan G2 adalah dua sub grafik yang tidak terhubung. Jadi kita akan memiliki jarak tak terbatas lagi. Kami akan menggunakan BFS untuk menghitung jarak maksimum antara node yang diberikan (u) ke semua node lain (v) yang dapat dijangkau dari u. Kemudian kita akan mengambil maksimum dari diameter yang dihitung sebelumnya dan hasilnya dikembalikan oleh BFS. Jadi kita akan memiliki diameter maksimum saat ini.

Analisis waktu berjalan:

1. O (| E |) menggunakan DFS
2. O (| E |) menggunakan DFS
3. BFS berjalan dalam waktu O (| E |).
4. Kita harus memanggil fungsi BFS untuk setiap dhuwur sehingga totalnya akan membutuhkan waktu O (| V || E |).

Total waktu = O (| v || E |) + O (| E |) + O (| E |)
Sejak | V || E | > | E |
jadi kami telah menjalankan waktu sebagai O (| v || E |).

BFS
DFS

Catatan: Ini bukan solusi elegan untuk masalah ini.