Project 5 FAQ

FAQ

• [Dec 6] Clearly, the DEBUG statement makes no sense. What should it be?

  Alas, heapToVertex and vertexToHeap are used for intermediate steps of Dijkstra's algorithm in the heap. Modify this to the following.

  DEBUG source
  

  This will print the heap after ONE step of Dijkstra's algorithm. This is the step AFTER the source vertex has been selected as the min cost vertex, and its neighbors "relaxed". For example, suppose source vertex A has neighbors B, C, and D with edge weights 3, 7, and 2 respectively. It should print out the information just after A has been selected and B, C, and D have their weights modified to 3, 7, and 2, and the heap has been re "heapified".

  You may write either a second version of "shortestPath" to handle this, or pass in a flag to shortestPath.

• [Dec 5] How do I figure out what to do?

  Figure out what data structurs you need (vector, array?). Figure out what the algorithm will do on a SPECIFIC example, and how it will update the graph.

• [Dec 5] How can I tell if Dijkstra's algorithm is working?

  Print the cost array after one pass of the algorithm and see which vertex it picks after that one pass. If it works for about two passes, you should be OK once you add it in a loop.

• [Dec 5] Do I have to write a PriorityQueue class? Can I just use a vector or array?

  It might be easier for the graders to determine you wrote a priority queue class if you wrote the class. You can declare the vector (or array) as a public member and access the variable directly.

  For example, if the public member is called "pqueue", then you can do:

  PriorityQueue pq;
  
  pq.pqueue.add( 1 );  // accessing public data member pqueue
  

  Or something to that effect.

• [Dec 5] Are the graphs directed or undirected?

  They are undirected. Notice that if vertex A has vertex B as a neighbor, then vertex B must have vertex A as a neighbor. HOWEVER, the input file may list only ONE of the two (though it could list both). Just because it lists one doesn't mean you only add one edge. You add edges in both directions.

  If both appear, they will have the same weight.

• [Dec 5] What about negative weight edges?

  You can assume there won't be any (no 0 weight edges).

• [Dec 5] What about self loops?

  You can assume there won't be any.

• [Dec 5] Do I need to implement Prim's algorithm?

  No. It's only in the tutorial because it was done last semester. Just implement Dijkstra.

• [Dec 5] How can we determine if a vertex is still in the Heap?

  The MinHeap is a template class. So, you can put an object that stores both the weight and the vertex number. Then, when call removeMin() it will tell you which vertex was removed from the heap. If you have a boolean array which has the same size as the number of vertices, you can set entry to the index to either false or true (flipping the value). This array can be stored outside the heap, as a local variable in, say, Dijstra's algorithm.

• [Dec 5] What should we set the edge weight to for "infinity" in Dijkstra's algorithm?

  Pick something large. 100,000 should be larger than any graph we will consider.

• [Dec 5] What should we do with getList()?

  You can get rid of it from your header file. I can't figure out why it's there.

Web Accessibility