Iskanje najcenejše poti v grafih preko polkolobarjevHorvat, Veronika (Avtor)
Oblak, Polona (Mentor)
Tropska algebrakvazi inverzBellmanov algoritemusmerjen grafV 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.20142014-09-16 16:05:01Diplomsko delo/naloga29471VisID: 14193sl