izpis_h1_title_alt

Iskanje najcenejše poti v grafih preko polkolobarjev
ID Horvat, Veronika (Author), ID Oblak, Polona (Mentor) More about this mentor... This link opens in a new window

.pdfPDF - Presentation file, Download (367,92 KB)
MD5: 8E4CA8F8C2AE7D44817AA4F2D68D705B
PID: 20.500.12556/rul/4654f995-6a38-4d26-8af7-9441b8fc1df4

Abstract
V diplomskem delu je predstavljen problem iskanja najcenejših poti v usmerjenem grafu s pomočjo Bellmanovega algoritma. Algoritem je različica Bellmanovih enačb z novostjo, da delo poteka nad matrikami in operacijami tropskega polkolobarja. Za utežen usmerjen graf cene povezav zapišemo v matriko A. Matrika ima kvazi inverz A^* nad tropskim polkolobarjem, s pomočjo katerega izračunamo minimalno rešitev sistema enačb, izraženega iz Bellmanovih enačb. Rešitev algoritma je vektor cen najcenejših poti do vseh vozlišč v grafu.

Language:Slovenian
Keywords:Tropska algebra, kvazi inverz, Bellmanov algoritem, usmerjen graf
Work type:Bachelor thesis/paper
Organization:FRI - Faculty of Computer and Information Science
Year:2014
PID:20.500.12556/RUL-29471 This link opens in a new window
Publication date in RUL:16.09.2014
Views:1488
Downloads:432
Metadata:XML RDF-CHPDL DC-XML DC-RDF
:
Copy citation
Share:Bookmark and Share

Secondary language

Language:English
Title:Semirings and the shortest path problem
Abstract:
The thesis presents the problem of finding the shortest path in a directed graph with the Bellman's algorithm. This algorithm a version of Bellman equation with the novelty that the we work with matrices and operations over tropical semiring. Given a weighted directed graph, its arc prices are written in a matrix A. The matrix has a quasi-inverse A^* over tropical semiring, which is used to compute the minimal solution of the system of equations expressed from the Bellman equation. The solution of the algorithm is a vector of prices that represents the prices of the shortest paths to all nodes in the graph.

Keywords:Tropical algebra, quasi inverse, Bellman's algorithm, directed graph

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections:

Back