Grafy a vyhladavanie (cv 9.)

Dijkstrov algoritmus

Mějme graf G, v němž hledáme nejkratší cestu. Řekněme, že V je množina všech vrcholů grafu G a množina E obsahuje všechny hrany grafu G. Algoritmus pracuje tak, že si pro každý vrchol v z V pamatuje délku nejkratší cesty, kterou se k němu dá dostat. Označme tuto hodnotu jako d[v]. Na začátku mají všechny vrcholy v hodnotu d[v]=∞, kromě počátečního vrcholu s, který má d[s]=0. Nekonečno symbolizuje, že neznáme cestu k vrcholu.

Dále si algoritmus udržuje množiny Z a N, kde Z obsahuje už navštívené vrcholy a N dosud nenavštívené. Algoritmus pracuje v cyklu tak dlouho, dokud N není prázdná. V každém průchodu cyklu se přidá jeden vrchol vmin z N do Z, a to takový, který má nejmenší hodnotu d[v] ze všech vrcholů v z N.

Pro každý vrchol u, do kterého vede hrana (označme její délku jako l(vmin,u)) z vmin, se provede následující operace: pokud (d[vmin] + l(vmin,u)) < d[u], pak do d[u] přiřaď hodnotu d[vmin] + l(vmin,u), jinak neprováděj nic.

Až algoritmus skončí, potom pro každý vrchol v z V je délka jeho nejkratší cesty od počátečního vrcholu s uložena v d[v].

Pseudokód

			   function Dijkstra(E, V, s):
			      for each vertex v in V:           // Inicializace
			          d[v] := infinity               // Zatím neznámá vzdálenost z počátku s do vrcholu v
			          p[v] := undefined              // Předchozí vrchol na nejkratší cestě z počátku s k cíli
			      d[s] := 0                          // Vzdálenost z s do s
			      N := V                             // Množina všech dosud nenavštívených vrcholů. Na začátku všech vrcholů.
			      while N is not empty:             // Samotný algoritmus
			         u := extract_min(N)            // Vezměme "nejlepší" vrchol                          
			          for each neighbor v of u:
			             alt = d[u] + l(u, v)       // v 1. smyčce cyklu u je s d[u] = 0
			             if alt < d[v]              
			                 d[v] := alt
			                 p[v] := u
        

V případě, že nás zajímá pouze nejkratší cesta mezi zdrojovým a cílovým vrcholem, můžeme ukončit hledání na řádce 9 if u = target. Cestu ze zdroje do cíle pak zjistíme cyklem:

			S := empty sequence 
		    u := target
			while defined p[u]
			    insert u at the beginning of S
			    u := p[u]
		

Zdroj: Wikipédia

Uloha 8

Pouzite kod z Ulohy 7 (Binarny vyhladavaci strom), ktory naplnite.

• 1. Potom vyvorite funkciu na Hladanie do hlbky s obmedzenim na zadanu hlbku.
• 2. Potom vyvorite funkciu na Hladanie do sirky.

Uloha 9

Vytvorte a naplnte

• 1. Neorientovaný graf
• 2. Orientovaný graf
• 3. Kladne Hranovo-ohodnotený graf

4. Naprogramujte Dijkstrov algoritmus a pouzite ho na najdenie najkratsej cesty z daneho uzla v kladne Hranovo-ohodnotenom grafe.

Uloha 10

Vytvorte a naplnte

• 1. Neorientovaný graf
• 2. Orientovaný graf
• 3. Hranovo-ohodnotený graf (nech obsahuje aj zaporne ohodnotenia)

4. Naprogramujte Bellman-Ford algoritmus a pouzite ho na najdenie najkratsej cesty z daneho uzla v Hranovo-ohodnotenom grafe (nech obsahuje aj zaporne ohodnotenia).

Checklist ;)

Prihláste sa s AIS ID a odškrtnite si úlohy čo ste už urobili a tým mi pomôžete zistiť ako stíhate na cvičení či aj mimo cvičenia.