Publication detail
Finding the Shortest Path in a Network with Uncertain Paths Lengths
ŠEDA, M.
Czech title
Hledání nejkratší cesty v síti s neurčitým ohodnocením tras
English title
Finding the Shortest Path in a Network with Uncertain Paths Lengths
Type
conference paper
Language
cs
Original abstract
Příspěvek se zabývá problémem hledání nejkratší cesty v grafu, jehož hrany jsou ohodnoceny fuzzy čísly. Protože operace určení minima fuzzy čísel založené na principu rozšíření vede k nedominovaným řešením, je navržen jiný přístup využívající pro porovnání fuzzy čísel Chengovu metodu středního bodu. Popsaný algoritmus je zobecněním Dijkstrova algoritmu pro deterministický případ.
Czech abstract
Příspěvek se zabývá problémem hledání nejkratší cesty v grafu, jehož hrany jsou ohodnoceny fuzzy čísly. Protože operace určení minima fuzzy čísel založené na principu rozšíření vede k nedominovaným řešením, je navržen jiný přístup využívající pro porovnání fuzzy čísel Chengovu metodu středního bodu. Popsaný algoritmus je zobecněním Dijkstrova algoritmu pro deterministický případ.
English abstract
In this paper, we deal with the shortest path problem (SPP) on a graph in which a fuzzy number, instead of a real number, is assigned to each edge. Since fuzzy min operation based on the extension principle leads to nondominated solutions, we propose another approach to solving the SPP using Cheng's centroid point fuzzy ranking method. The described algorithm is a fuzzy generalization of Dijkstra's algorithm for the deterministic case.
Keywords in English
single shortest path problem, fuzzy ranking, binary heap, priority queue
RIV year
2001
Released
01.11.2001
Publisher
AD&M Ostrava
Location
Ostrava
ISBN
80-238-7812-3
Book
Sborník přednášek k 6. ročníku konference Inteligentní systémy pro praxi
Pages count
8
BIBTEX
@inproceedings{BUT6632,
author="Miloš {Šeda},
title="Hledání nejkratší cesty v síti s neurčitým ohodnocením tras",
booktitle="Sborník přednášek k 6. ročníku konference Inteligentní systémy pro praxi",
year="2001",
month="November",
publisher="AD&M Ostrava",
address="Ostrava",
isbn="80-238-7812-3"
}