Zaawansowane algorytmy i struktury danych/Ćwiczenia 6: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
Linia 2: Linia 2:
 
{{kotwica|zadanie 1|}}
 
{{kotwica|zadanie 1|}}
  
Pokaż, że [[../Wykład 6#iloczyn_odległości|iloczyn odległości]] jest przemienny względem dodawania, tzn, że dla macierzy <math>C</math>, <math>D</math>
+
Pokaż, że [[../Wykład 6#iloczyn_odległości|iloczyn odległości]] jest przemienny względem dodawania, tzn. że dla macierzy <math>C</math>, <math>D</math>
 
i <math>E</math> rozmiaru <math>n\times n</math>zachodzi:
 
i <math>E</math> rozmiaru <math>n\times n</math>zachodzi:
  
Linia 28: Linia 28:
  
  
Zaproponuj jak wykorzystać algorytm Bellmana-Forda do sprawdzenia, czy w grafie <math>G=(V,E)</math> i wagach krawędzi opisanych funkcją <math>w:E \to \mathcal{R}</math> istnieje cykl o ujemnej wadze.
+
Zaproponuj, jak wykorzystać algorytm Bellmana-Forda do sprawdzenia, czy w grafie <math>G=(V,E)</math> i wagach krawędzi opisanych funkcją <math>w:E \to \mathcal{R}</math> istnieje cykl o ujemnej wadze.
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
Dodaj nowy wierzchołek <math>s</math> i skonstruuj graf <math>G'=(V',E')</math> i
+
Dodaj nowy wierzchołek <math>s</math> i skonstruuj graf <math>G'=(V',E')</math> oraz
 
funkcję wagową <math>w'</math> taką, że:
 
funkcję wagową <math>w'</math> taką, że:
 
{{wzor2|
 
{{wzor2|

Aktualna wersja na dzień 19:38, 24 wrz 2006

Zadanie 1

Pokaż, że iloczyn odległości jest przemienny względem dodawania, tzn. że dla macierzy , i rozmiaru zachodzi:



oraz


Wskazówka

Zadanie 2


Zaproponuj, jak wykorzystać algorytm Bellmana-Forda do sprawdzenia, czy w grafie i wagach krawędzi opisanych funkcją istnieje cykl o ujemnej wadze.

Rozwiązanie


Zadanie 3

Mając dane graf , funkcję wagową , odległości z wybranego wierzchołka do w grafie , zaproponuj algorytm obliczania drzewa najkrótszych ścieżek w czasie


Wskazówka