Implementing optimization idea for Dijkstra's algorithm

[crystality]

Hi!

I'm trying to implement an optimization idea for Dijkstra's algorithm for homework. This is the optimization idea that they want us to implement:

Idea 3. Many of the vertices have exactly two neighbors. If a vertex v has exactly two neighbors u and w, then you can replace the two edges (u, v) and (v, w) with a single edge (u, w) whose length is the sum of the lengths of the two original edges. This reduces the number of vertices and edges in the graph. The challenge here is keeping track of the new edges and their corresponding constituent edges. Also, you will have to be careful to make sure that vertex v is not the requested source or destination.

This is my code so far: http://pastebin.com/d20f8dfc6
And these are relevant/included files: graph.cpp | graph.h | CPUTimer.h | shortestPaths.out (sample executable) | BinaryHeap.h | BinaryHeap.cpp | dsexceptions.h | vector.cpp | vector.h

So I've implemented Dijkstra's, and I've implemented the first two "optimization" ideas that my professor gave us. That works fine. But I'm stuck on how to do optimization idea #3. Lines 94-108 of my code is where I try to do that. I can compile it, but when I run the program, it gets stuck... So I have that commented out.

Oh, and I apologize in advance for my messy code. I pretty much stuck everything in one function. Sorry! Hope you can still help. Thanks. =)

[crystality]

Oops, I have some information to add:

• This is the assignment
• Sample graph with 87575 vertices and 121961 edges: usa.txt
• Sample graph with 6 vertices and 10 edges: input6.txt

Thanks for your help!