Generalized path-finding algorithms on semirings and the fuzzy shortest path problem

摘要

A new dioid structure <Ω_k,?,?,ε,e> is proposed to solve a path-finding problem in a fuzzy graph. This algebraic structure is adapted precisely to solve the problem of the K-best fuzzy shortest paths. We demonstrate that the generalized Gauss-Seidel's algorithm always converges for the solving of the K-best fuzzy shortest paths problem on a valued fuzzy graph without cycles of negative weight. This work starts a safe extension of the path algebra paradigm to valued fuzzy graphs for the shortest path-finding problem.