15,965,165 members
See more:
Hi everyone, I am struggling with a graph algorithm problem in my Data Structures Lab assignment.

I am given a weighted graph with N number of vertices. We have a starting point and we want to travel and visit as much vertices as possible, but within a given maximum weight. Do you have an algorithm for that?

P.S. I am familiar with C++, so I will really appreciate it if you solve this problem with C++.

What I have tried:

Someone said to me that the problem can be solved with simple Dijkstra Search, but I don't see how the shortest path between two nodes can solve this problem.
I also tried to figure if it can be solved with Prim's or Kruskal's algorithms, but no luck.
Posted
Updated 27-Dec-21 9:31am
Greg Utas 26-Dec-21 18:43pm
The algorithms that you mention deal with spanning trees, but it sounds like you want a path. Is that correct?
It does not necessarily have to be a path. The problem is to visit as many vertices as possible, within a given distance. It does not matter if a circuit is formed or not
Greg Utas 28-Dec-21 6:45am
See Solution 2, which may significantly help to optimize the code. If you find the minimal spanning tree and then do what I suggested, I think you'll find the same walk as if you applied my suggestion to the entire graph.

## Solution 2

This problem is discussed in the book Algorithms in C++ volume 5 - Graph Algorithms. I believe your solution is going to be based on minimal spanning trees. The chapter on this topic (chap 20) is very detailed. I think if you can see it, then you will have more direction to go to solve your problem. I enjoy graph theory and wish I could answer more but I can't. I do own the book I referenced if you need some help.

Minimum spanning tree - Wikipedia[^]

v2
Greg Utas 28-Dec-21 6:47am
5. Finding the MST sounds like a good way to start. See my above comment.
Andy Bantly 28-Dec-21 13:22pm
Yeah - Too bad this student has a teacher that threw them the min flow problem without much history. The "hello world" of flow traversal. :)

## Solution 1

I can't see a way to do this except for an exhaustive search (depth-first recursion) from the starting point.

Exclude an edge when it has already been traversed in the same direction. When you can't add another edge, compare the number of vertices in the current walk with the number in the best walk so far. If the current walk reached more, it becomes the candidate solution. If it reached the same number, it becomes the candidate if its cost is less.

A walk ends when it (a) cannot add another edge without exceeding the maximum cost or (b) has reached all vertices.

When you back up to a previous vertex, the edge in question becomes available again in the original direction.

If you display what your program is doing during its search, you may find some optimizations. But without writing the code, I can't think of any.

## Solution 3

Quote:
I will really appreciate it if you solve this problem with C++

Do you understand that you are basically required to create a solution by- yourself ?
And not necessarily the optimum algorithm.

Quote:
Someone said to me that the problem can be solved with simple Dijkstra Search, but I don't see how the shortest path between two nodes can solve this problem.

As far as I understand, it is not "Dijkstra shortest path" algorithm.