|
| |
|
|
Application of the Dijkstra's Algorithm in the Pedestrian Flow Problem
Petrášová, Tereza ; Felcman, Jiří (advisor) ; Dolejší, Vít (referee)
The purpose of this work is to study the pedestrian flow equations as the coupled system formed by the eikonal equation and the first order hyperbolic system with the source term. The hyperbolic system consists of the continuity equation and the equations of motion of a compressible inviscid fluid. To specify the outer volume forces in the latter equation it is assumed that the pedestrians try to move in a desired direction with a desired velocity, which are dependent on the density in their surroundings. The desired direction is obtained as the gradient of the solution of the eikonal equation. We show that the solution of the eikonal equation has the meaning of the time needed to pass the fastest path to the exit. We suggest avoiding solving the eikonal equation by using the graph theory, where as the graph we use the underlying triangulation. The norm of each edge in the graph is density-dependent and has the dimension of time. This is together with the use of the modified Dijkstra's algorithm the novelty of the work. Numerical results of the two approaches are presented. Powered by TCPDF (www.tcpdf.org)
|
|
| |
|
|
Graph Theory in Economic Practice
Geško, Dávid ; Půža, Bedřich (referee) ; Novotná, Veronika (advisor)
In Bachelor’s thesis we deal with Traveling salesman person problem. In theoretical part are introduced basic terms of graphs theory and methods to solve Traveling salesman person problem. Practical part draws a comparison among efficiency of several methods solving this problem in environment of real world examples. In summary analysis are these methods evaluated and consequently chosen and implemented most effective method for company, which want to use it to determining most optimized tours for distributing goods.
|
|
|
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.
|
|
|
Shopping Advisor
Kocourek, Jakub ; Bartík, Vladimír (referee) ; Kolář, Dušan (advisor)
The attached bachelor thesis deals with nding the shortest ways in a shop for the selected purchase. The different technologies of creating web pages are described. As for the state space search algorithms are given for nding the shortest path between two points and for solving the travel salesmen problem. The thesis continues with the description of a design and implementation of application with all used technologies (PHP, Nette, MySQL, JS, JQuery) applying the Dijkstra's algorithm for nding the shortest path and genetic algorithm for solving the travel salesmen problem.
|
|
|
Demonstration of Graph Algorithms
Varadinek, Jakub ; Zámečníková, Eva (referee) ; Křivka, Zbyněk (advisor)
This bachelor thesis deals with the development of the application for demonstration and visualization of several graph algorithms. The application allows the user to create a graph, rate edges or name and layout vertices. The individual algorithms can be performed in created graph for visual observation how the algorithm works. There is also the possibility of stepping through the chosen algorithm and an interactive mode where next steps are selected by the user and the application checks the correctness of these steps.
|
|
|
Shortest Paths in a Graph
Krauter, Michal ; Křivka, Zbyněk (referee) ; Masopust, Tomáš (advisor)
This thesis deals with shortest paths problem in graphs. Shortest paths problem is the basic issue of graph theory with many pracitcal applications. We can divide this problem into two following generalizations: single-source shortest path problem and all-pairs shortest paths problem. This text introduces principles and algorithms for generalizations. We describe both classical and new more efficient methods. It contains information about how some of these algorithms were implemented and offers an experimental comparison of these algorithms.
|
|
|
Systems for remote measurement in power engineering
Hudec, Lukáš ; Mlýnek, Petr (referee) ; Mišurec, Jiří (advisor)
The work deals with the measurement and management in power. Provides an introduction to the problems of remote meter reading, management, and describes the current situation in the field of modern technologies Smart metering and Smart grids. It also analyzed the issue of collection of networks and data collection from a large number of meters over a wide area. For the purpose of data transmission are described GPRS, PLC, DSL, ... Further, there are given options to streamline communication. This area is used hierarchical aggregation. Using k-means algorithm is a program designed to calculate the number of concentrators and their location in the group of meters. The finished program is written in Java. It has a graphical interface and shows how the calculation is conducted. To verify the results of the optimization program is given simulation model in OPNET Modeler tool. Audited results are described in the conclusion and can deduce that using the optimization program is to streamline communications.
|
|
|
Map search engines and their algorithms
Jedlička, Jan ; Chlapek, Dušan (advisor) ; Kuncová, Martina (referee)
This diploma paper, as it results from its title, it puts mind to map search engines and concerning algorithms. It describes two key algorithms, which solve the graph shortest path problem: Dijkstra's algorithm and Floyd-Warshall algorithm, which are specialized on solution procedure and running time of algorithms. A separate chapter is dedicated to map systems in GPS equipments. In the diploma paper the map search engines are described generally; it compares selected applications and examines how the shortest path problem is solved in practice with those applications -- searching for route in between two places on the map. The diploma paper describes the importance of geographic information systems generally, but particularly it concentrates on map services of GIS.
|
guest ::
