WSEAS Transactions on Computers
Print ISSN: 1109-2750, E-ISSN: 2224-2872
Volume 14, 2017
Optimal Paths of Knapsack-Set Vertices on a Weight-Independent Graph
Author:
Abstract: Two problems that are often studied and researches in computer science algorithms are the knapsack problem and the shortest paths on weighted graphs problem. Their combination is often addressed by dynamic programming solutions for the knapsack problem, using shortest path problem, with the creation of a knapsack graph. But these researches consider only two aspects of weight and value for an item/vertex, and here we 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). Every vertex in this specific graph is a set of knapsack items. This situation is viable for real-life circumstances, in which a path has a non-dependent attribute (physical distance, travel time, etc.), and there are different kinds of items to be picked in different locations on this path. The problem presented here is finding the most efficient path between two vertices (source and target), in three aspects- minimal edge wise, maximum knapsack value wise, and a combination of maximal efficiency for both properties. An algorithm for finding these optimal paths is presented here along with specific explanations on its decision stages, and several examples for it.
Search Articles
Keywords: Knapsack problem, Shortest paths on weighted graphs, Dijkstra’s algorithm, 0-1 knapsack problem, All paths between two vertices in a graph
Pages: 163-171
WSEAS Transactions on Computers, ISSN / E-ISSN: 1109-2750 / 2224-2872, Volume 14, 2017, Art. #18