Najkratšia cesta
orientovaný graf: dvojica G = (V, E), kde E ? V ? V
hrana z vrcholu i do j: dvojica (i, j) ? E
cesta: postupnost na seba nadväzujúcich hrán
cyklus: cesta z vrcholu i do i
váhovaný graf: graf, v ktorom kazdá cesta má celocíselnú váhu (tiez ohodnotený graf)
dlzka cesty: suma všetkých hrán na ceste (ich váh)
váhová matica: (váhovaného grafu s N vrcholmi) je matica W typu N ? N, v ktorej W[i, j] =
- váha hrany (i, j), ak (i, j) ? E
- 0, ak i = j
- ?, ak i ? j ? (i, j) ? E
prázdna cesta: z vrcholu i do j vzdy exsituje; jej dlzka: ?
Problém najkratších ciest:
- daný je váhovaný graf G a jeho váhová matica
- G neobsahuje cykly s negatívnou dlzkou
- vypocítat maticu D typu N ? N, v ktorej D[i, j] = dlzka najkratšej cesty z vrcholu i do j
- hodnotu D[i, j] budeme nazývat vzdialenost i, j
- ak neexistuje cesta z vrcholu i do j, tak D[i, j] = ?