Iskanje najcenejše poti v grafih preko polkolobarjev : diplomsko delo

Horvat, Veronika (avtor), Oblak, Polona (mentor)

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.

• Jezik: Slovenski jezik
• Ključne besede: tropska algebra, kvazi inverz, Bellmanov algoritem, usmerjen graf, računalništvo, računalništvo in informatika, univerzitetni študij, diplomske naloge
• Vrsta gradiva: Diplomsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Založnik: [V. Horvat]
• Leto izida: 2014
• Št. strani: 31 str.
• PID: 20.500.12556/RUL-68835
• UDK: 004.4:512(043.2)
• COBISS.SI-ID: 1536062403
• Datum objave v RUL: 10.07.2015

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Semirings and the shortest path problem

Izvleček

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.

• Ključne besede: tropical algebra, quasi inverse, Bellman's algorithm, directed graph, computer science, computer and information science, diploma