- Tytuł:
- Lazy shortest path computation in dynamic graphs
- Autorzy:
- Aioanei, D.
- Powiązania:
- https://bibliotekanauki.pl/articles/305443.pdf
- Data publikacji:
- 2012
- Wydawca:
- Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
- Tematy:
-
single-source shortest path
dynamic graph
livewire
active snake
interactive image segmentation - Opis:
- We address the problem of single-source shortest path computation in digraphs with non-negative edge weights subjected to frequent edge weight decreases such that only some shortest paths are requested in-between updates. We optimise a recent semidynamic algorithm for weight decreases previously reported to be the fastest one in various conditions, resulting in important time savings that we demonstrate for the problem of incremental path map construction in usersteered image segmentation. Moreover, we extend the idea of lazy shortest path computation to digraphs subjected to both edge weight increases and decreases, comparing favourably to the fastest recent state-of-the-art algorithm.
- Źródło:
-
Computer Science; 2012, 13 (3); 113-137
1508-2806
2300-7036 - Pojawia się w:
- Computer Science
- Dostawca treści:
- Biblioteka Nauki
Artykuł