Algorytm dewiacyjny dla problemu wyznaczania K najkrótszych ścieżek

Streszczenie. Jednym z badanych problemow teorii grafow jest problem wyznaczenia najkrotszej ściezki. Rozszerzeniem tego problemu jest problem wyznaczenia K (K > 1) najkrotszych ściezek. Badane są dwa warianty tego problemu. W pierwszym dopuszcza sie wyznaczenie ściezek zawierających cykle, a w drugim są wyznaczane wylącznie ściezki acykliczne. W pracy zostal przedstawiony algorytm dewiacyjny, umozliwiający wyznaczenie K najkrotszych ściezek, ktore mogą zawierac cykle. Slowa kluczowe: skierowany graf wazony, ściezka, podściezka, waga ściezki, najkrotsza ściezka, K najkrotszych ściezek, drzewo ściezek, algorytm Dijkstry