Taqsimlangan algoritmlar va tizimlar” fanidan mustaqil ish №3

Amalga oshirish [ tahrirlash ]

Amalga oshirish ko'plab dasturlash tillari uchun mavjud .

• 
  C++ uchun boost:: graph kutubxonasida
  
• 
  C# uchun QuickGraph da
  
• 
  C# uchun , QuickGraphPCL da (Portativ sinf kutubxonalaridan foydalangan holda loyihalar bilan yaxshiroq mos keladigan QuickGraph vilkasi.)
  
• 
  Java uchun , Apache Commons Graph kutubxonasida
  
• 
  JavaScript uchun Cytoscape kutubxonasida _
  
• 
  MATLAB uchun , Matlab_bgl paketida
  
• 
  Perl uchun Grafik modulida _
  
• 
  Python uchun SciPy kutubxonasida (modul scipy.sparse.csgraph ) yoki NetworkX kutubxonasida
  
• 
  R uchun , e1071 va Rfast paketlarida
  

Boshqa eng qisqa yo'l algoritmlari bilan taqqoslash [ tahrirlash ]

Floyd-Uorshall algoritmi zich grafiklardagi cho'qqilarning barcha juftlari orasidagi yo'llarni hisoblash uchun yaxshi tanlov bo'lib , unda ko'pchilik yoki barcha cho'qqi juftlari qirralar bilan bog'langan. Manfiy bo'lmagan chekka og'irliklari bo'lgan siyrak grafiklar uchun har bir mumkin bo'lgan boshlang'ich cho'qqidan Dijkstra algoritmini ishga tushirish orqali past asimptotik murakkablikni olish mumkin , chunki takrorlangan Dijkstraning eng yomon ish vaqti ({\displaystyle O(|E||V|+|V|^{2}\log |V|)} Fibonachchi vayronalari yordamida ) dan kichikroq{\ displaystyle O(|V|^{3})} Floyd-Uorshall algoritmining ishlash vaqti qachon{\displaystyle |E|} dan sezilarli darajada kichikdir{\displaystyle |V|^{2}} . Manfiy qirralari bo'lgan, ammo manfiy sikllari bo'lmagan siyrak grafiklar uchun Jonson algoritmidan foydalanish mumkin, bunda takroriy Dijkstra yondashuvi kabi asimptotik ish vaqti bir xil bo'ladi.
Bundan tashqari , zich grafiklarda barcha juftliklarning eng qisqa yo'llarini hisoblashni tezlashtirish uchun tez matritsalarni ko'paytirishdan foydalanadigan ma'lum algoritmlar mavjud , ammo ular odatda chekka og'irliklar bo'yicha qo'shimcha taxminlarni keltirib chiqaradi (masalan, ularni kichik butun sonlar bo'lishini talab qilish). ^[15] [16] Bundan tashqari, ularning ishlash vaqtidagi yuqori doimiy omillar tufayli ular juda katta grafiklar uchun faqat Floyd-Uorshall algoritmiga nisbatan tezlikni taʼminlaydi.