|
The Shortest Graph's Pahts Finding
Jágr, Petr ; Ohlídal, Miloš (referee) ; Jaroš, Jiří (advisor)
The aim of this thesis is finding, comparing and implementation of algorithms for finding the shortest paths between each of pairs of nodes in a graph. For this task I use modifications of existing algorithms to achive the lowest time consumption of the computation. Modifications are established on Dijkstra's and Floyd-Warshall's algorithm. We also familiarize with Bellman-Ford algorithm.
|
|
Searching for optimal path in graphs
Znamenáčková, Gabriela ; Lachout, Petr (advisor) ; Kopa, Miloš (referee)
It's possible to simulate a lot of real decision-making situations by a weighted graph. Consequently it's important to find the optimal solution of a given situation based on this model. The subject of this Bachelor Thesis is to present the typical problems of combinatorial optimization, that deal with finding the optimal path in a graph considering the given conditions, and algorithms to find their optimal solution. It's focused on following problems: the shortest path problem, the minimum cost spanning-tree problem, the minimum cost Steiner tree problem, the travelling salesman problem and the optimal network flow. Working of some algorithms is shown on illustrative examples.
|
|
Searching for optimal path in graphs
Znamenáčková, Gabriela ; Lachout, Petr (advisor) ; Kopa, Miloš (referee)
It's possible to simulate a lot of real decision-making situations by a weighted graph. Consequently it's important to find the optimal solution of a given situation based on this model. The subject of this Bachelor Thesis is to present the typical problems of combinatorial optimization, that deal with finding the optimal path in a graph considering the given conditions, and algorithms to find their optimal solution. It's focused on following problems: the shortest path problem, the minimum cost spanning-tree problem, the minimum cost Steiner tree problem, the travelling salesman problem and the optimal network flow. Working of some algorithms is shown on illustrative examples.
|
|
The Shortest Graph's Pahts Finding
Jágr, Petr ; Ohlídal, Miloš (referee) ; Jaroš, Jiří (advisor)
The aim of this thesis is finding, comparing and implementation of algorithms for finding the shortest paths between each of pairs of nodes in a graph. For this task I use modifications of existing algorithms to achive the lowest time consumption of the computation. Modifications are established on Dijkstra's and Floyd-Warshall's algorithm. We also familiarize with Bellman-Ford algorithm.
|