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.