diplomsko delo
Veronika Horvat (Avtor), Polona Oblak (Mentor)

Povzetek

Iskanje najcenejše poti v grafih preko polkolobarjev

Ključne besede

tropska algebra;kvazi inverz;Bellmanov algoritem;usmerjen graf;računalništvo;računalništvo in informatika;univerzitetni študij;diplomske naloge;

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.11 - Diplomsko delo
Organizacija: UL FRI - Fakulteta za računalništvo in informatiko
Založnik: [V. Horvat]
UDK: 004.4:512(043.2)
COBISS: 1536062403 Povezava se bo odprla v novem oknu
Št. ogledov: 73
Št. prenosov: 5
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Semirings and the shortest path problem
Sekundarni povzetek: 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.
Sekundarne ključne besede: tropical algebra;quasi inverse;Bellman's algorithm;directed graph;computer science;computer and information science;diploma;
Vrsta datoteke: application/pdf
Vrsta dela (COBISS): Diplomsko delo/naloga
Študijski program: 1000468
Komentar na gradivo: Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani: 31 str.
ID: 8739379