9.1 Deykstra alqoritminin iş prinsipləri
Deykstra alqoritmi — başlanğıc zirvədən bütün digər zirvələrə qədər ən qısa yolları tapmaq üçün istifadə olunan bir alqoritmdir, burada qrafın kənarlarının çəkisi müsbət olmalıdır. Alqoritm hər addımda başlanğıc zirvədən ən kiçik məlum məsafəsi olan zirvəni seçərək və qonşu zirvələrə olan məsafələri yeniləyərək greedy yanaşma tətbiq edir.
Alqoritmin addımları:
1. İlkinləşdirmə:
- Başlanğıc zirvəyə olan məsafəni 0 olaraq təyin edirik.
- Bütün digər zirvələrə olan məsafəni sonsuz təyin edirik.
- Ziyarət edilməmiş zirvələrin çoxluğunu yaradırıq.
2. Cari zirvənin seçilməsi:
- Ziyarət edilməmiş zirvələrdən ən kiçik məsafəyə malik olanını seçirik (ilk addımda başlanğıc zirvə).
3. Məsafələrin yenilənməsi:
- Cari zirvənin hər bir qonşusu üçün, əgər cari zirvə vasitəsi ilə olan yeni yol əvvəlki məlum yoldan qısa olarsa, həmin zirvəyə olan məsafəni yeniləyirik.
4. Cari zirvəni ziyarət edilmiş kimi işarələyirik:
- Cari zirvəni ziyarət edilməmiş zirvələr çoxluğundan çıxarırıq.
5. 2-4-cü addımları təkrarlayırıq, bütün zirvələr ziyarət edilənə qədər və ya hədəf zirvəyə çatana qədər.
Deykstra alqoritminin vaxt və yaddaş mürəkkəbliyi:
Vaxt mürəkkəbliyi:
O((V + E) log V) əgər bir priority queue (məsələn, Fibonacci heap) istifadə olunarsa, burada V — zirvələrin sayı, E — kənarların sayı.
O(V^2) əgər məsafələrin saxlanması üçün sadə siyahı istifadə olunarsa.
Yaddaş mürəkkəbliyi:
O(V) məsafələri və ancestor-ları (yolun bərpası üçün) saxlamaq üçün.
9.2 Dijkstra alqoritminin reallaşdırılması
Dijkstra alqoritminin reallaşdırılması uzun olsa da, çox sadədir. Tövsiyə edərdim ki, bunu başa düşməyə çalış. Əgər çətinlik çəkirsənsə, bir az yuxarı qayıdıb alqoritmin əsas addımlarını yenidən oxu.
Prioritetli növbə (heap) istifadə edərək Dijkstra alqoritminin reallaşdırılması nümunəsi:
import heapq
def dijkstra(graph, start):
# Başlanğıc
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
priority_queue = [(0, start)]
parents = {vertex: None for vertex in graph}
while priority_queue:
current_distance, current_vertex = heapq.heappop(priority_queue)
# Əgər cari məsafə artıq yazılmış məsafədən böyükdürsə, növbəti zirvəyə keçirik
if current_distance > distances[current_vertex]:
continue
# Qoşulmuş zirvələrə məsafələrin yenilənməsi
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
# Əgər qoşulu zirvəyə daha qısa yol tapılıbsa
if distance < distances[neighbor]:
distances[neighbor] = distance
parents[neighbor] = current_vertex
heapq.heappush(priority_queue, (distance, neighbor))
return distances, parents
# İstifadə nümunəsi:
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
start_vertex = 'A'
distances, parents = dijkstra(graph, start_vertex)
print("Başlanğıc zirvədən ən qısa məsafələr:", distances)
print("Yolu bərpa etmək üçün valideynlər:", parents)
Nəticə:
Başlanğıc zirvədən ən qısa məsafələr: {'A': 0, 'B': 1, 'C': 3, 'D': 4}
Yolu bərpa etmək üçün valideynlər: {'A': None, 'B': 'A', 'C': 'B', 'D': 'C'}
9.3 Dijkstra alqoritmindən istifadə edərək həll olunan məsələlərin nümunələri
Dijkstra alqoritmindən istifadə edərək həll olunan məsələlərin klassik nümunələri:
1. Nəqliyyat şəbəkələrində marşrutların optimallaşdırılması
Nəqliyyat şəbəkəsində (məsələn, şəhərlər arasında) nöqtələr arasında ən qısa yolu tapmaq.
Tətbiq:
Google Maps kimi naviqasiya sistemləri optimal marşrutların hesablanması üçün Dijkstra alqoritmindən istifadə edirlər.
2. Çatdırılma marşrutlarının planlaşdırılması
Malların çatdırılması xidmətləri üçün marşrutların optimallaşdırılması, beləliklə, xərcləri və çatdırılma vaxtını minimuma endirmək.
Tətbiq:
Logistika şirkətləri çatdırılma marşrutlarını planlaşdırmaq və əməliyyat xərclərini azaltmaq üçün Dijkstra alqoritmindən istifadə edirlər.
3. Şəbəkələrin idarə olunması
Məlumat paketlərinin kompüter şəbəkələrində istiqamətləndirilməsini optimallaşdırmaq üçün gecikmələri minimuma endirmək və ötürmə qabiliyyətini artırmaq.
Tətbiq:
OSPF (Open Shortest Path First) kimi istiqamətləndirmə protokolları şəbəkələrdə ən qısa yolları tapmaq üçün Dijkstra alqoritmindən istifadə edir.
4. Sosial şəbəkələrin analizi
Sosial qrafiklərdə ən qısa yolların tapılması və mərkəziliyin ölçülməsi (məsələn, ən təsirli istifadəçiləri tapmaq üçün).
Tətbiq:
Sosial platformalar istifadəçilər arasındakı əlaqələri analiz edərək tövsiyələr təqdim etmək və şəbəkə fəaliyyətini nəzərdən keçirmək üçün istifadə edirlər.
5. Oyunlar və virtual dünyalar
Maneələr və müxtəlif çətinlik səviyyələri ilə oyun dünyalarında personajların yol tapması.
Tətbiq:
Oyun mühərrikləri personajların və obyektlərin virtual dünyalarda hərəkətini hesablaması üçün Dijkstra alqoritmindən istifadə edir.
6. Enerji idarəetmə sistemləri
Enerji şəbəkələrində enerji paylanmasının optimallaşdırılması üçün itkiləri minimuma endirmək və təchizatın etibarlılığını təmin etmək.
Tətbiq:
Elektroenerji şirkətləri enerji şəbəkələrində enerji ötürmə marşrutlarının optimallaşdırılması, itkilərin minimuma endirilməsi və yüklənmələrdən yayınmaq üçün Dijkstra alqoritmindən istifadə edirlər.
Nümunə:
Elektrik şəbəkələrində hər bir düyün elektrik yarımstansiyasını, qollar isə müxtəlif müqavimət səviyyələrinə malik elektrik xətlərini təmsil edir. Dijkstra alqoritmi enerji mənbəyindən istehlakçıya ən az müqavimətə malik yolu tapmağa kömək edir.
7. Təhliyə və yol planlaşdırma sistemləri
Fövqəladə hallar zamanı insanları təhlükəsiz şəkildə və tez bir zamanda çıxarmaq üçün binalarda və ya şəhərlərdə təhliyə marşrutlarının optimallaşdırılması.
Tətbiq:
Memarlar və mühəndislər təhliyə marşrutlarının planlaşdırılması üçün Dijkstra alqoritmindən istifadə edirlər ki, bu da insanların təhlükəli zonalardan tez və təhlükəsiz şəkildə çıxarılmasını təmin edir.
Nümunə:
Çoxmənzilli binada və ya ofis binasında qrafın düyünləri otaqları və dəhlizləri, qollar isə onların arasındakı yolları təmsil edir. Dijkstra alqoritmi binadakı istənilən nöqtədən ən yaxın çıxışa qədər ən qısa yolu tapmaq üçün istifadə edilə bilər.
GO TO FULL VERSION