DaniWeb Forum Index > Software Development > C++

C++ RSS

Quick question -

Thread Solved

•

Join Date: Apr 2008

Posts: 185

Reputation: DemonGal711 is an unknown quantity at this point

Solved Threads: 10

DemonGal711 DemonGal711 is offline

Offline

Junior Poster

Quick question -

Nov 19th, 2008

Ok, working on a program to find the shortest path between two points. Simple.

Now, we are going to be given a list like this to denote the start and end, and then the weight of the lines.

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
A   D
B  C  31
B  A  4
C  A  12
C  D  3
A   D
B  C  31
B  A  4
C  A  12
C  D  3

That bunch of coding produces a picture that looks like this. click here

Now. I figured I'd use something like an array to hold the points, and then have a pointer or something like that that points to each thing. Like, A -> AB = 4 & A -> AC = 12. Then I figured you'd use a stack to keep track of the direction you went (not sure if this would be needed but figured it would be the best way to handle this).

Does my pointer thing sound like a good idea or should I use a tree or something like that. Also, is there a way that I could store AB = 12 and then have it say that finding AB is also like finding BA. Basically, I think that would eliminate my need of pointers.

Thanks in advance.

•

Join Date: Oct 2008

Posts: 1,839

Reputation: ddanbe has much to be proud of

Solved Threads: 266

ddanbe

Offline

Posting Virtuoso

Re: Quick question -

Nov 19th, 2008

Maybe you get some ideas from Prim's algorithm. Read http://en.wikipedia.org/wiki/Prim%27s_algorithm

Today is a gift, that's why it is called "The Present".
Make love, no war. Cave ab homine unius libri.
Danny

•

Join Date: Sep 2004

Posts: 7,540

Reputation: Narue has a reputation beyond repute

Solved Threads: 704

Narue

Offline

Code Goddess

Re: Quick question -

Nov 19th, 2008

>I figured I'd use something like an array to hold the points
Since this is a graph problem, so you need to hold the identity of the vertex (A, B, C, etc...), the the vertices that a vertex is connected to through an edge (A->B, A->C, B->C, etc...), and the weight of the edge (B->C=31, A->B=4, C->D=3, etc...). As long as you can represent all of that information, it really doesn't matter how you handle the storage. However, an adjacency matrix or adjacency list would be a good start, if you've studied those at this point.

>Then I figured you'd use a stack to keep track of the direction you went
Sounds good to me. You can also treat this as a more sophisticated find_min algorithm. When you find a path that's smaller than the current path, make a copy of the stack and the total weight so you can print the result:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
stack<Vertex> min;
 
for (int i = 0; i < n_paths; i++ ) {
  // The magic is in weigh_graph ;-)
  stack<Vertext> curr = weigh_path ( graph, i );
 
  if ( min.empty() || weight ( curr ) < weight ( min ) )
    min = curr;
}
 
show_path ( min );
stack<Vertex> min;

for (int i = 0; i < n_paths; i++ ) {
  // The magic is in weigh_graph ;-)
  stack<Vertext> curr = weigh_path ( graph, i );

  if ( min.empty() || weight ( curr ) < weight ( min ) )
    min = curr;
}

show_path ( min );

To help you do research, this is called the single pair shortest path problem. Several good algorithms already exist for solving it, but this assignment may be to get you to come up with something on your own.

I'm here to prove you wrong.

•

Join Date: Apr 2008

Posts: 185

Reputation: DemonGal711 is an unknown quantity at this point

Solved Threads: 10

DemonGal711 DemonGal711 is offline

Offline

Junior Poster

Re: Quick question -

Nov 19th, 2008

Yeah, I think the purpose is to make us write out our own cause he already knows we understand how to do it, he just wants us to show we can tell the computer how to do it.

Heh, just learned the matrices, so I'll use that. Could I have the weights stored within the matrix cell by use of a struct.

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
struct cell
{ int val;
  int weight; };
struct cell
{ int val;
  int weight; };

Then have it search through the row of the vertex I've been at (like A) for all the val == 1 and compare the weight of each to figure out what the lowest would be (like how A->B = 4 and A->C = 12). Or would it be better to do the adjacency list and have the each cell point to something (array for example) that stores the weight?

Another question, say that the values were as listed below, same picture, just changing weights.
BA = 31
BC = 1
CA = 4
CD = 19
If you go by the lowest value. It would tell you to go from A->C->B, then it would see that C->D is a better choice, pop out B, and push D. Is that an issue I should worry about since it wastes computer time (I know it isn't that much, but my teacher is a stickler for making a program as fast as it can be). I mean, if there was an edge BD, I wouldn't care cause it might be shorter, but the fact that there is one path automatically tells you that if you get to C, you need to go to D next.

Last edited by DemonGal711; Nov 19th, 2008 at 4:16 pm.

•

Join Date: Sep 2004

Posts: 7,540

Reputation: Narue has a reputation beyond repute

Solved Threads: 704

Narue

Offline

Code Goddess

Re: Quick question -

Nov 19th, 2008

>Is that an issue I should worry about since it wastes computer time
If you can get away with an optimization, go for it. But keep in mind that you can be given any number of graphs, you're not just solving the problem for this one graph, so the optimization has to be generic enough to work across the board.

I'm here to prove you wrong.

•

Join Date: Apr 2008

Posts: 185

Reputation: DemonGal711 is an unknown quantity at this point

Solved Threads: 10

DemonGal711 DemonGal711 is offline

Offline

Junior Poster

Re: Quick question -

Nov 19th, 2008

Yeah, I know, I think my teacher gives us these just to annoy me...

I figured I'd do something like this, just using the above as an example

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
check row D (or the row the end vertex is at)
edges = number of 1's in that row
if (edges == 1) 
   point = the vertex that touches end vertex   
   once at point, go to end
 
check row D (or the row the end vertex is at)
edges = number of 1's in that row
if (edges == 1) 
   point = the vertex that touches end vertex   
   once at point, go to end

That's basically all I'd tell it to do, nothing too fancy.

Last edited by DemonGal711; Nov 19th, 2008 at 4:22 pm.

•

Join Date: Apr 2008

Posts: 185

Reputation: DemonGal711 is an unknown quantity at this point

Solved Threads: 10

DemonGal711 DemonGal711 is offline

Offline

Junior Poster

Re: Quick question -

Nov 24th, 2008

Okay, I've got another question. I decided to make a large graph so that my program can handle something like that without any issue. Now, the problem is that the graph I made makes my computer jump all over the place. Here's the image if you want to see what I was trying to do. If I did it right and didn't mess anything up, the shortest path from A to U should be
A E J M P S T U
http://i21.photobucket.com/albums/b2...c/Picture1.gif

The problem I'm having is that my teacher suggested we use a stack. To me that seems like a waste in my example cause you start with A. E is the shortest path (5) so you push E. From E you go to J (5+4=9). J only leads to M (11). AB was 10, so the program should go back, pop out E, and push B. However, I need it to remember that E is still a vertex that we need to check the points with, cause once you move to either C or D, you're up to 12 which means that A->E->J->M is better (since it equals 11). Thus meaning my stack would have to pop out B, and put in E, J, and M.

It's like, I would need a stack of values that is the shortest, and an array that stores the vertexes that we have gone to that need to be evaluated when looking for a short path.