| Summary: | Standard approaches for finding the cost and the path of problems in graphs are based on algorithms relying the fulfilment of certain algebraic properties such associativity and distributivity, for instance the multiplication of matrices. This thesis presents an investigation on the implementation of functional paradigm approach to tackle the problem in the lack of the distributivity property for pathfinding problems in graphs.
The literature on the application, design and implementation, of this approach is scarce. The order in which a bicriteria optimization problem is selected affects the fulfilment of at least one of the properties in the calculation for pathfinding problems.
Two well-known algorithms, Dijkstra’s shortest path and Floyd-Roy-Warshall all-pairs, are adapted and tuned for their application to the problems investigated here, Maximum Capacity (or Bottleneck)-Shortest path and knapsack problem.
The performance of the functional approach is assessed and results are bench- marked by two evaluations methods, eager and lazy. Also the application of the derived functions into the existing algorithms are evaluated in both pure and imperative-functional versions.
|
|---|