W zależności od ilości danych do przetworzenia generowanie pliku może się wydłużyć.

Jeśli generowanie trwa zbyt długo można ograniczyć dane np. zmniejszając zakres lat.

Artykuł

Pobierz BibTeX

Tytuł

Review and Performance Analysis of Shortest Path Problem Solving Algorithms

Autorzy

[ 1 ] Katedra Sieci Telekomunikacyjnych i Komputerowych, Wydział Elektroniki i Telekomunikacji, Politechnika Poznańska | [ P ] pracownik

Rok publikacji

2014

Opublikowano w

International Journal on Advances in Software

Rocznik: 2014 | Tom: vol. 7 | Numer: no. 1&2

Typ artykułu

artykuł naukowy

Język publikacji

angielski

Słowa kluczowe
EN
  • shortest path
  • algorithms
  • review
  • performance
  • analysis
Streszczenie

EN The development of concepts derived from the generic approach to solving the problem of the shortest path resulted in numerous and various algorithms that appeared over the past decades. The studies on the most basic operation aimed at the determination of the shortest path between two given points in a graph (in other words, often a network) have resulted in sophisticated solutions designed for more and more demanding applications. Those include finding the sets of paths with the shortest distance between all pairs of nodes or searching for a shortest path tree. The aim of the present article is to give the reader an introduction to the problem of the shortest path and a detailed review of two groups of selected algorithms designed to solve particular problems. In the study described herein, different algorithms have been examined for their efficacy in their operation in directed graphs of different type represented in a well-defined data structure. The empirical simulation-based analysis proves that the performance varies among algorithms under investigation and allows to suggest, which methods ought to be used to solve specific variants of the shortest path problem and which algorithms should be avoided or used with caution.

Strony (od-do)

20 - 30

URL

http://www.iariajournals.org/software/soft_v7_n12_2014_paged.pdf#page=20

Ta strona używa plików Cookies, w celu zapamiętania uwierzytelnionej sesji użytkownika. Aby dowiedzieć się więcej przeczytaj o plikach Cookies i Polityce Prywatności.