Quick question -

[DemonGal711]

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.

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.

[ddanbe]

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

[Narue]

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

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.

[DemonGal711]

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.

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.

[Narue]

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

[DemonGal711]

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

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.

[DemonGal711]

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/b272/DemonGal711/Program%20Pic/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.