There have been several combinations of the knapsack problem and the shortest paths on weighted graph problems in different researches. The combination is often used to describe the choices made during the knapsack problem stages using dynamic programming methods, by using the knapsack graph. But these researches consider only two aspects of weight and value for an item/vertex. The objective of this paper is to address a different kind of problem in which we are taking into consideration three properties: item weight, item value and edge weight (that connects two items, but its weight is not depended on its vertices). The problem presented here is finding the most efficient path between two vertices of this specific kind of graph, in three aspects- minimal edge wise, maximum knapsack value wise, and a combination of maximal efficiency of both properties. This is done through an object oriented method, in which every path of the graph, between two chosen vertices, has comparable attributes, that gives us the ability to prefer a certain path from another. An algorithm for finding these optimal paths is presented here, along with specific explanations on its decision stages, and several examples for it. The results were achieved an exact paradigm for the integrated problem, taking into consideration any desired aspect, and achieving optimal choices per each attribute.
展开▼
