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"
}