#TITLE_ALTERNATIVE#

• Main Author: NYOMAN SUKAJAYA (NIM 23596009), I
• Format: Theses
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/10678
• Institution: Institut Teknologi Bandung

A new version of auction algorithm for finding a shortest path from single origin to many destinations in the directed graph has been implemented in a software which is called SPPAR. Shortest Path Auction with Reduction allows us to solve more general problems by adding to contraction or extension operations a graph reduction, that is, deleting unnecessary arcs of the digraph. Since all arcs incoming to a terminal node except its unique predecessor arc on path are deleted in the graph reduction step, it is possible to break out such a close cycle as created at auction approach for shortest path. At all iterations, the algorithm maintains multi paths starting at the origin. Finding an initial price vector which satisfies complementary slackness is done through preprocessing. At each iteration, reduction of the graph is performed preceeding extension or contraction operations. Besides, the algorithm also includes infeasibility test. The shortest path of node from the origin in the reduced graph as a result of execution is the same as its shortest path in the original graph.