Sieci teleinformatyczne Algorytm Dijkstry ćw3 PDF

Preview

Summary

Jedno z pięciu sprawozdań na przedmiot Sieci teleinformatyczne....

Description

Uniwersytet Technologiczno - Przyrodniczy im. Jana i Jędrzeja Śniadeckich w Bydgoszczy

Wydział Telekomunikacji, Informatyki i Elektrotechniki

Szymon Kaźmierczak nr albumu: 115855

Jan Stypczyński Nr albumu: 114904

Ćwiczenie nr 3 Algorytm Dijkstry

Sprawozdanie na przedmiot: Sieci teleinformatyczne Prowadzący: dr inż. Ireneusz Olszewski

1. Cel ćwiczenia: Zapoznanie się z działaniem Algorytmu Dijkstry. 2. Wstęp teoretyczny: Graf nieskierowany - podstawowy obiekt rozważań teorii grafów, struktura matematyczna służąca do przedstawiania i badania relacji między obiektami. W uproszczeniu graf to zbiór wierzchołków, które mogą być połączone krawędziami w taki sposób, że każda krawędź kończy się i zaczyna w którymś z wierzchołków. Graf skierowany (digraf)– zbiór wierzchołków i zbiór krawędzi skierowanych łączących (co najwyżej jeden raz) uporządkowane pary wierzchołków. Mówimy wtedy, że krawędź łączy pierwszy wierzchołek z drugim (albo, że prowadzi od pierwszego wierzchołka do drugiego). Droga – ścieżka, w której wierzchołki są różne (z wyjątkiem ewentualnej równości wierzchołków pierwszego i ostatniego – mamy wtedy do czynienia ze szczególnym rodzajem drogi, drogą zamkniętą, tzw. cyklem). Niech dany będzie graf nieskierowany G z wagami i wyróżnionym wierzchołkiem v. Drzewem minimalnych ścieżek (ozn. SPT shortest paths tree) nazywamy drzewo z korzeniem v w którym każda droga od wierzchołka v do pozostałych wierzchołków jest najkrótszą drogą w grafie G. Graf ważony (inaczej graf z wagami) to taki graf, w którym każdej krawędzi przypisana jest pewna wartość liczbowa. Wartość ta może oznaczać np. długość krawędzi lub jej przepustowość. Algorytm Dijkstry – algorytm służący do wyznaczania najkrótszych ścieżek w grafie. Wyznacza najkrótsze ścieżki z jednego wierzchołka (zwanego wierzchołkiem źródłowym) do pozostałych wierzchołków. Algorytm wymaga, aby wagi krawędzi grafu nie były ujemne. Autorem algorytmu jest holenderski naukowiec Edsger Dijkstra. Złożoność obliczeniowa - miara służąca do porównywania efektywności algorytmów. Mamy dwa kryteria efektywności: • czas, • pamięć. Pseudo kod: Dane wejściowe: w n a e

– – – –

macierz przechowująca krawędzie oraz wagi liczba wierzchołków wierzchołek początkowy (źródło) wierzchołek docelowy (odpływ)

Inicjalizacja: forv ∈ c do begin

dist(c)∞; final(c)false; pred(c)-1 end; dist(a) 0; final(a)true; recenta; Iteracja: while final(e) = false do begin for każdego bezpośredniego następnika v wierzchołka recent, jeśli not final(c) do begin newlabeldist(recent) +wrecent,v; if newlabel...