Generalised arrays and shortest path problems
Claudio Sandi · ACM SIGAPL APL Quote Quad · 1986
Real world problems are often formulated as flow optimization problems on large networks, with thousands of nodes but with a restricted number of arcs. The average number of arcs having a given node as origin or terminal node (node degree) may be limited even to a few units. Standard optimization methods, mainly matrix methods for complete or strongly connected graphs, may become unpractical; recent results have shown the superiority of advanced methods based on suitable data structures. In this study the classical shortest path problem, one of the basic techniques in network flow optimization, is approached, in APL environment, using: i) standard matrix methods, ii) methods that handle irregular structures element by element, and iii) advanced methods using generalized arrays. Preliminary results indicate which approach should be preferred, according to problem characteristics and size.