Metody rozwiązywania problemu najkrótszych dróg wierzchołkowo rozłącznych przechodzących przez wybrane wierzchołki w sieciach o strukturze kraty

W pracy zaprezentowano modele i metody służące do rozwiązywania problemu wyznaczania K dróg wierzchołkowo rozłącznych przechodzących przez wybrane wierzchołki, o najmniejszym sumarycznym koszcie w sieci prostokątnej (tzw. kracie) opartej o graf G. Zdefiniowano problem jako zadanie optymalizacji liniowej ciągłej oraz przedstawiono dwie metody przybliżone jego rozwiązania: metodę SGDP (bazującą na pewnej iteracyjnej procedurze wyznaczania dróg najkrótszych w podgrafach grafu G) oraz modyfikację metody Edmondsa-Karpa rozwiązywania problemu wyznaczania przepływu zaspokajającego o minimalnym koszcie. Przeprowadzono analizę ich złożoności oraz dokonano porównania jakości obu metod na podstawie eksperymentalnych wyników.

In the paper, models and methods for solving K node-disjoint shortest paths visiting specified nodes problem in mesh networks (based on a graph G) have been presented. The problem has been defined as continuous linear programming problem and two approximation methods for solving it have been presented: SGDP method (based on some iterative procedure of finding shortest paths in subgraphs of G) and modification of Edmond's-Karp method for solving minimal cost flow problem. Complexity and quality analysis of presented methods based on experimental results using real terrain models have been done.