Near-Shortest Simple Paths on a Network with Imprecise Edge Weights

Abstract

We present an algorithm to obtain the near-shortest simple (cycle free) paths between a pair of specified vertices s and t on a network whose edge weights are of imprecise nature. In particular, we have considered the weights as interval numbers and triangular fuzzy numbers. Existing ideas on addition and comparison between two imprecise numbers of same types are introduced. Initially, a fuzzy optimal path is obtained to which the decision-maker always satisfies with different grades of satisfaction. On the basis of the obtained fuzzy shortest path, different sets of nearshortest simple paths are produced within specified tolerance limit. Retaining only the first k such paths according to their weights, the k-shortest simple paths problem is also solved.