I am a matrix that represents the shortest path between any two nodes, which I compute from a weighted adjacency matrix using Floyd Warshall algorithm. Additionally, I have a constant maximum weight. My goal is to find the path that maximizes the number of vertices visited, while enforcing that the final total path weight is less than or equal to the weight limit. One option would be to generate all permutations, but this would be exponential time, no?
Another thought was to apply dynamic programming with subproblems defined as the max number of nodes from met from node i to node j subject to the constraint. Finally, I thought to reduce this to a linear programming problem with variables equal to edges. Then, would it be equivalent to the kidney exchange problem? After I check that there are no negative cycles, does this imply that there will be no cycles in the final optimal path? Please let me know if I can clarify any part of the problem.
I create the shortest path matrix with the following function:
def floyd_warshall(G):
n = len(G)
# run a modified Bellman-Ford's algorithm on `G`
for k in range(n):
for i in range(n):
for j in range(n):
# if better path is found, relax
if G[i][j] > G[i][k] + G[k][j]:
G[i][j] = G[i][k] + G[k][j]
return G