ON ASSOCIATIVE SHORTEST PATH PROBLEMS
| Autor: | Yukihiro Maruyama |
|---|---|
| Rok vydání: | 1997 |
| Předmět: |
associative binary operation
Computer science Ocean Engineering directed network Longest path problem Combinatorics Euclidean shortest path Shortest Path Faster Algorithm Shortest path problem shortest path problems K shortest path routing acyclic digraphs Yen's algorithm Distance Constrained Shortest Path First |
| Zdroj: | Bulletin of informatics and cybernetics. 29:67-81 |
| ISSN: | 0286-522X |
| DOI: | 10.5109/13462 |
| Popis: | We consider a wide class of shortest path problems in acyclic digraphs. In the problems, the length of a path is defined by using an associative binary operation. We derive recursive equations in dynamic programming for the problems, which involve additive, multiplicative, multiplicative-additive, minimum and fractional shortest path problems. A necessary and sufficient condition and two sufficient conditions for the recursive equation to have a solution are given because for all problems the recursive equation does not hold. In case the equation has a solution, a sequence which converges to the solution is proposed. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|