Need help with a graph problem

Question

0.00/5 (No votes)

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 26-Dec-21 6:58am

Dawood Ahmad 2021

Updated 27-Dec-21 9:31am

Add a Solution

Comments

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?

Dawood Ahmad 2021 26-Dec-21 19:25pm

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.

3 solutions

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Patrice T · Answer 1 · 2021-12-27T09:31:00

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.

Andy Bantly · Answer 2 · 2021-12-27T06:46:00

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[^]

Posted 27-Dec-21 6:46am

Andy Bantly64K

Updated 27-Dec-21 6:48am

v2

Comments

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. :)

Greg Utas · Answer 3 · 2021-12-26T14:28:00

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.

Need help with a graph problem

3 solutions

Solution 3

Solution 2

Solution 1

Add your solution here

Preview 0

Need help with a graph problem

3 solutions

Solution 3

Solution 2

Solution 1

Add your solution here

Preview 0

Existing Members

...or Join us