Publication detail

Fuzzy All-Pairs Shortest Paths Problem

ŠEDA, M.

Czech title

Problém hledání všech nejkratších cest ve fuzzy grafu

English title

Fuzzy All-Pairs Shortest Paths Problem

Type

book chapter

Language

en

Original abstract

In this paper, we deal with the All-Pairs Shortest Paths Problem (APSPP) on a graph in which a fuzzy number, instead of a real number, is assigned to each edge. Since the fuzzy min operator based on the extension principle leads to nondominated solutions, we propose another approach to solving the APSPP using a suitable fuzzy ranking method. We also show that the efficiency of computations may be improved by the proposed APSPP modification of the Dijkstra algorithm based on a binary heap data structure.

Czech abstract

V příspěvku se zabýváme hledáním nejkratších cest mezi všemi dvojicemi vrcholů grafu, kde ohodnocení hran grafu není dáno deterministicky, ale je vyjádřeno fuzzy čísly. Protože operace určení minima na fuzzy číslech využívající princip rozšíření vede k nedominovaným řešením, navrhujeme jiný přístup využívající vhodnou metodu srovnávání fuzzy čísel. Rovněž ukážeme, že efektivitu výpočtu řešení daného problému lze zvýšit modifikací Dijkstrova algoritmu založeného na datové struktuře binární halda.

English abstract

In this paper, we deal with the All-Pairs Shortest Paths Problem (APSPP) on a graph in which a fuzzy number, instead of a real number, is assigned to each edge. Since the fuzzy min operator based on the extension principle leads to nondominated solutions, we propose another approach to solving the APSPP using a suitable fuzzy ranking method. We also show that the efficiency of computations may be improved by the proposed APSPP modification of the Dijkstra algorithm based on a binary heap data structure.

Keywords in Czech

problém nejkratší cesty, fuzzy číslo, binární halda

Keywords in English

shortest path problem, fuzzy number, binary heap

Released

01.09.2006

Publisher

Springer-Verlag

Location

Berlin, Germany

ISBN

978-3540347804

Book

Reusch, B. (ed.): Computational Intelligence, Theory and Applications

Edition number

1

Pages from–to

395–404

Pages count

10

BIBTEX


@inbook{BUT55645,
  author="Miloš {Šeda},
  title="Fuzzy All-Pairs Shortest Paths Problem",
  booktitle="Reusch, B. (ed.): Computational Intelligence, Theory and Applications",
  year="2006",
  month="September",
  pages="395--404",
  publisher="Springer-Verlag",
  address="Berlin, Germany",
  isbn="978-3540347804"
}