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