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