Detail publikace
Problém hledání všech nejkratších cest ve fuzzy grafu
ŠEDA, M.
Český název
Problém hledání všech nejkratších cest ve fuzzy grafu
Anglický název
Fuzzy All-Pairs Shortest Paths Problem
Typ
kapitola v knize
Jazyk
en
Originální abstrakt
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.
Český abstrakt
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.
Anglický abstrakt
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.
Klíčová slova česky
problém nejkratší cesty, fuzzy číslo, binární halda
Klíčová slova anglicky
shortest path problem, fuzzy number, binary heap
Vydáno
01.09.2006
Nakladatel
Springer-Verlag
Místo
Berlin, Germany
ISBN
978-3540347804
Kniha
Reusch, B. (ed.): Computational Intelligence, Theory and Applications
Číslo edice
1
Strany od–do
395–404
Počet stran
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"
}