Premium
An algebra for determining all path‐values in a network with application to K‐shortest‐paths problems
Author(s) -
Wongseelashote A.
Publication year - 1976
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230060403
Subject(s) - shortest path problem , linear algebra , mathematics , algebra over a field , generalization , path (computing) , elementary algebra , numerical linear algebra , k shortest path routing , schedule , division (mathematics) , discrete mathematics , computer science , numerical analysis , pure mathematics , arithmetic , graph , mathematical analysis , geometry , programming language , operating system
This paper presents an algebra which is appropriate for the formulation and solution of k‐Shortest‐paths problems. The algebra is a generalization of “Schedule Algebra” studied by Giffler [3,4] for computing path values in a network. It is shown formally that these path values can be calculated by using direct methods of numerical linear algebra for solving systems of linear equations and an algorithm similar to the long division procedure of ordinary arithmetic. Such a method is then modified to yield an algorithm for finding k shortest elementary paths in a network.