A Complex Problem of Knapsack and Shortest Paths on Weighted Graphs

there are two problems in computer science algorithms, the knapsack problem and the shortest paths on weighted graphs problem, that are well-known and researched in the past decades. A complex problem that combines these two, as a two-step problem on the same entities, is the main idea and subject of this paper, in which this combination will be presented, along with several examples for it. Index terms- Knapsack problem, Shortest paths on weighted graphs, Dijkstra's algorithm, Dantzig greedy approximation algoriths, graph theory.