Last Revised 5/21/02 at 12:01am. DYKSTRA'S ALGORITHM: A WORKED EXAMPLE CAUTION: MAKE SURE THAT YOU UNDERSTAND ANY CODE THAT YOU USE. IT HAS NOT BEEN TESTED. Use Dykstra's algorithm to find the minimum cost path from the start node to the destination node in the following graph: +-+ 9 +-+ start -->|0|-----|2|<-- destination +-+ /+-+ | / | 1| 7/ |3 | / | +-+/ +-+ |1|-----|3| +-+ 2 +-+ Use the following classes: // data members in class CNode class CEdge // view class. { { int nnodes, nedges; public: public: int start; CPoint location; int from; int dest; BOOL permanent; int to; int lastmadeperm; int totalcost; int cost; int state; int prevnode; }; int min, minnode; int nedgesout; int edgeout[5]; State constants: CNode(); ADDNODES CNode(CPoint); ADDEDGES void Display(CDC *); SETSTART }; SETDEST Here are the suggested main menu entries: AddNodes AddEdges SetStart SetDest DoDykstra Reset When ? is shown, the variable is uninitialized. Use a large value for infinity (INF) like 1000000 in edge[i], i=0,1,2,... An asterisk (*) by a node means that it has been made permanent. --------------------------------------------------------------------------------- 1. Situation after adding all the nodes, and setting the start and dest nodes. The data members min and minnode are uninitialized until DoDykstra where they are first needed. +-+ +-+ loc.x loc.y perm totcost prev nedges edge[0] edge[1] edge[2] |0| |2| +=====+=====+====+=======+=====+=====+=======+=======+=======+ +-+ +-+ 0 | 100 100 F INF -1 0 -1 -1 -1 | 1 | 100 200 F INF -1 0 -1 -1 -1 | 2 | 200 100 F INF -1 0 -1 -1 -1 | 3 | 200 200 F INF -1 0 -1 -1 -1 | +-+ +-+ +============================================================+ |1| |3| lastmade +-+ +-+ from to cost start dest perm state +=====+=====+=====+ +=====+=====+========+========+ +=====+=====+=====+ 0 2 -1 ADDNODES ---------------------------------------------------------------------------------- 2. After adding edge from Node 0 to Node 1 (Cost 1) NOTE: Each edge is represented as two directed edges in the CEdge array. +-+ +-+ loc.x loc.y perm totcost prev nedges edge[0] edge[1] edge[2] |0| |2| +=====+=====+====+=======+====+=====+=======+=======+=======+ +-+ +-+ 0 | 100 100 F INF -1 1 0 -1 -1 | | 1 | 100 200 F INF -1 1 1 -1 -1 | 1| 2 | 200 100 F INF -1 0 -1 -1 -1 | | 3 | 200 200 F INF -1 0 -1 -1 -1 | +-+ +-+ +===========================================================+ |1| |3| lastmade +-+ +-+ from to cost start dest perm state +=====+=====+=====+ +=====+=====+========+========+ 0 | 0 1 1 | 0 2 -1 ADDEDGES 1 | 1 0 1 | +=====+=====+=====+ ---------------------------------------------------------------------------------- 3. After adding edge from Node 1 to Node 3 (Cost 2) +-+ +-+ loc.x loc.y perm totcost prev nedges edge[0] edge[1] edge[2] |0| |2| +=====+=====+====+=======+====+======+=======+=======+=======+ +-+ +-+ 0 | 100 100 F INF -1 1 0 -1 -1 | | 1 | 100 200 F INF -1 2 1 2 -1 | 1| 2 | 200 100 F INF -1 0 -1 -1 -1 | | 3 | 200 200 F INF -1 1 3 -1 -1 | +-+ +-+ +============================================================+ |1|-----|3| lastmade +-+ 2 +-+ from to cost start dest perm state +=====+=====+=====+ +=====+=====+========+========+ 0 | 0 1 1 | 0 2 -1 ADDEDGES 1 | 1 0 1 | 2 | 1 3 2 | 3 | 3 1 2 | +=====+=====+=====+ ---------------------------------------------------------------------------------- 4. After adding edge from Node 3 to Node 2 (Cost 3) +-+ +-+ loc.x loc.y perm totcost prev nedges edge[0] edge[1] edge[2] |0| |2| +=====+=====+====+=======+====+======+=======+=======+=======+ +-+ +-+ 0 | 100 100 F INF -1 1 0 -1 -1 | | | 1 | 100 200 F INF -1 2 1 2 -1 | 1| |3 2 | 200 100 F INF -1 1 5 -1 -1 | | | 3 | 200 200 F INF -1 2 3 4 -1 | +-+ +-+ +============================================================+ |1|-----|3| lastmade +-+ 2 +-+ from to cost start dest perm state +=====+=====+=====+ +=====+=====+========+========+ 0 | 0 1 1 | 0 2 -1 ADDEDGES 1 | 1 0 1 | 2 | 1 3 2 | 3 | 3 1 2 | 4 | 3 2 3 | 5 | 2 3 3 | +=====+=====+=====+ ---------------------------------------------------------------------------------- 5. After adding edge from Node 1 to Node 2 (Cost 7) +-+ +-+ loc.x loc.y perm totcost prev nedges edge[0] edge[1] edge[2] |0| |2| +=====+=====+====+=======+====+======+=======+=======+=======+ +-+ /+-+ 0 | 100 100 F INF -1 1 0 -1 -1 | | / | 1 | 100 200 F INF -1 3 1 2 6 | 1| 7/ |3 2 | 200 100 F INF -1 2 5 7 -1 | | / | 3 | 200 200 F INF -1 2 3 4 -1 | +-+/ +-+ +============================================================+ |1|-----|3| lastmade +-+ 2 +-+ from to cost start dest perm state +=====+=====+=====+ +=====+=====+========+========+ 0 | 0 1 1 | 0 2 -1 ADDEDGES 1 | 1 0 1 | 2 | 1 3 2 | 3 | 3 1 2 | 4 | 3 2 3 | 5 | 2 3 3 | 6 | 1 2 7 | 7 | 2 1 7 | +=====+=====+=====+ ---------------------------------------------------------------------------------- 6. After adding edge from Node 0 to Node 2 (Cost 9) +-+ 9 +-+ loc.x loc.y perm totcost prev nedges edge[0] edge[1] edge[2] |0|-----|2| +=====+=====+====+=======+====+======+=======+=======+=======+ +-+ /+-+ 0 | 100 100 F INF -1 2 0 8 -1 | | / | 1 | 100 200 F INF -1 3 1 2 6 | 1| 7/ |3 2 | 200 100 F INF -1 3 5 7 9 | | / | 3 | 200 200 F INF -1 2 3 4 -1 | +-+/ +-+ +============================================================+ |1|-----|3| lastmade +-+ 2 +-+ from to cost start dest perm state +=====+=====+=====+ +=====+=====+========+========+ 0 | 0 1 1 | 0 2 -1 ADDEDGES 1 | 1 0 1 | 2 | 1 3 2 | 3 | 3 1 2 | 4 | 3 2 3 | 5 | 2 3 3 | 6 | 1 2 7 | 7 | 2 1 7 | 8 | 0 2 9 | 9 | 2 0 9 | +=====+=====+=====+ ---------------------------------------------------------------------------------- We now start with the execution of DoDykstra. The edge array will not change for this phase, so it will no longer be displayed. Also, the state data member is not needed. 7. Initialization of totalcost nodearray[0].totalcost = 0; +-+ 9 +-+ loc.x loc.y perm totcost prev nedges edge[0] edge[1] edge[2] |0|-----|2| +=====+=====+====+=======+====+======+=======+=======+=======+ +-+ /+-+ 0 | 100 100 F 0 -1 2 0 8 -1 | | / | 1 | 100 200 F INF -1 3 1 2 6 | 1| 7/ |3 2 | 200 100 F INF -1 3 5 7 9 | | / | 3 | 200 200 F INF -1 2 3 4 -1 | +-+/ +-+ +============================================================+ |1|-----|3| +-+ 2 +-+ lastmade start dest perm state min minnode +=====+=====+========+=========+========+=======+ 0 2 -1 notneeded ? ? ---------------------------------------------------------------------------------- 8. Determine minimum totcost of all nodes not yet made permanent (min), keeping track of the node where the minimum cost occurred (minnode). This node is made permanent. min = INF; minnode = -1; for(i=0; i < nnodes; i++) if(!nodearray[i].permanent && nodearray[i].totalcost < min) { min = nodearray[i].totalcost; minnode = i; } nodearray[minnode].permanent = TRUE; lastmadeperm = minnode; +-+ 9 +-+ loc.x loc.y perm totcost perm nedges edge[0] edge[1] edge[2] *|0|-----|2| +=====+=====+====+=======+====+======+=======+=======+=======+ +-+ /+-+ 0 | 100 100 T 0 -1 2 0 8 -1 | | / | 1 | 100 200 F INF -1 3 1 2 6 | 1| 7/ |3 2 | 200 100 F INF -1 3 5 7 9 | | / | 3 | 200 200 F INF -1 2 3 4 -1 | +-+/ +-+ +============================================================+ |1|-----|3| +-+ 2 +-+ lastmade start dest perm state min minnode +=====+=====+========+=========+========+=======+ 0 2 0 notneeded 0 0 ----------------------------------------------------------------------------------- 9. Update the total cost of the first edge out of the node last made permanent in 9 and 10: for(i = 0; i < nodearray[lastmadeperm].nedges; i++) { nextedge = nodearray[lastmadeperm].edge[i]; nextnode = edgearray[nextedge].to; newcost = nodearray[lastmadeperm].totalcost + edgearray[nextedge].cost; if (!nodearray[nextnode].permanent && newcost < nodearray[nextnode].totalcost) { nodearray[nextnode].totalcost = newcost; nodearray[nextnode].prev = lastmadeperm; } } +-+ 9 +-+ loc.x loc.y perm totcost perm nedges edge[0] edge[1] edge[2] *|0|-----|2| +=====+=====+====+=======+====+======+=======+=======+=======+ +-+ /+-+ 0 | 100 100 T 0 -1 2 0 8 -1 | | / | 1 | 100 200 F 1 -1 3 1 2 6 | 1| 7/ |3 2 | 200 100 F INF -1 3 5 7 9 | | / | 3 | 200 200 F INF -1 2 3 4 -1 | +-+/ +-+ +============================================================+ |1|-----|3| +-+ 2 +-+ lastmade start dest perm state min minnode +=====+=====+========+=========+========+=======+ 0 2 0 notneeded 0 0 ----------------------------------------------------------------------------------- 10. Update the total cost of the second edge out of the node last made permanent: +-+ 9 +-+ loc.x loc.y perm totcost perm nedges edge[0] edge[1] edge[2] *|0|-----|2| +=====+=====+====+=======+====+======+=======+=======+=======+ +-+ /+-+ 0 | 100 100 T 0 -1 2 0 8 -1 | | / | 1 | 100 200 F 1 0 3 1 2 6 | 1| 7/ |3 2 | 200 100 F 9 0 3 5 7 9 | | / | 3 | 200 200 F INF -1 2 3 4 -1 | +-+/ +-+ +============================================================+ |1|-----|3| +-+ 2 +-+ lastmade start dest perm state min minnode +=====+=====+========+=========+========+=======+ 0 2 0 notneeded 0 0 ----------------------------------------------------------------------------------- 11. Find min and minnode of all edges not yet made permanent. Make minnode permanent. +-+ 9 +-+ loc.x loc.y perm totcost perm nedges edge[0] edge[1] edge[2] *|0|-----|2| +=====+=====+====+=======+====+======+=======+=======+=======+ +-+ /+-+ 0 | 100 100 T 0 -1 2 0 8 -1 | | / | 1 | 100 200 T 1 0 3 1 2 6 | 1| 7/ |3 2 | 200 100 F 9 0 3 5 7 9 | | / | 3 | 200 200 F INF -1 2 3 4 -1 | +-+/ +-+ +============================================================+ *|1|-----|3| +-+ 2 +-+ lastmade start dest perm state min minnode +=====+=====+========+=========+========+=======+ 0 2 1 notneeded 1 1 ----------------------------------------------------------------------------------- 12. Update the total cost of the first edge out of the node last made permanent: +-+ 9 +-+ loc.x loc.y perm totcost perm nedges edge[0] edge[1] edge[2] *|0|-----|2| +=====+=====+====+=======+====+======+=======+=======+=======+ +-+ /+-+ 0 | 100 100 T 0 -1 2 0 8 -1 | | / | 1 | 100 200 T 1 0 3 1 2 6 | 1| 7/ |3 2 | 200 100 F 9 0 3 5 7 9 | | / | 3 | 200 200 F 3 -1 2 3 4 -1 | +-+/ +-+ +============================================================+ *|1|-----|3| +-+ 2 +-+ lastmade start dest perm state min minnode +=====+=====+========+=========+========+=======+ 0 2 1 notneeded 1 1 ----------------------------------------------------------------------------------- 13. Update the total cost of the second edge out of the node last made permanent: +-+ 9 +-+ loc.x loc.y perm totcost prev nedges edge[0] edge[1] edge[2] *|0|-----|2| +=====+=====+====+=======+====+======+=======+=======+=======+ +-+ /+-+ 0 | 100 100 T 0 -1 2 0 8 -1 | | / | 1 | 100 200 T 1 0 3 1 2 6 | 1| 7/ |3 2 | 200 100 F 8 1 3 5 7 9 | | / | 3 | 200 200 F 3 1 2 3 4 -1 | +-+/ +-+ +============================================================+ *|1|-----|3| +-+ 2 +-+ lastmade start dest perm state min minnode +=====+=====+========+=========+========+=======+ 0 2 1 notneeded 1 1 ----------------------------------------------------------------------------------- 14. Find min and minnode of all edges not yet made permanent. Make minnode permanent. +-+ 9 +-+ loc.x loc.y perm totcost prev nedges edge[0] edge[1] edge[2] *|0|-----|2| +=====+=====+====+=======+====+======+=======+=======+=======+ +-+ /+-+ 0 | 100 100 T 0 -1 2 0 8 -1 | | / | 1 | 100 200 T 1 0 3 1 2 6 | 1| 7/ |3 2 | 200 100 F 8 1 3 5 7 9 | | / | 3 | 200 200 T 3 1 2 3 4 -1 | +-+/ +-+ +============================================================+ *|1|-----|3|* +-+ 2 +-+ lastmade start dest perm state min minnode +=====+=====+========+=========+=======+=======+ 0 2 3 notneeded 3 3 ----------------------------------------------------------------------------------- 15. Update the total cost of the only edge out of the node last made permanent: +-+ 9 +-+ loc.x loc.y perm totcost prev nedges edge[0] edge[1] edge[2] *|0|-----|2| +=====+=====+====+=======+====+======+=======+=======+=======+ +-+ /+-+ 0 | 100 100 T 0 -1 2 0 8 -1 | | / | 1 | 100 200 T 1 0 3 1 2 6 | 1| 7/ |3 2 | 200 100 F 6 1 3 5 7 9 | | / | 3 | 200 200 T 3 1 2 3 4 -1 | +-+/ +-+ +============================================================+ *|1|-----|3|* +-+ 2 +-+ lastmade start dest perm state min minnode +=====+=====+========+=========+=======+=======+ 0 2 3 notneeded 3 3 ----------------------------------------------------------------------------------- 16. Find min and minnode of all edges not yet made permanent. Make minnode permanent. +-+ 9 +-+ loc.x loc.y perm totcost prev nedges edge[0] edge[1] edge[2] *|0|-----|2|* +=====+=====+====+=======+====+======+=======+=======+=======+ +-+ /+-+ 0 | 100 100 T 0 -1 2 0 8 -1 | | / | 1 | 100 200 T 1 0 3 1 2 6 | 1| 7/ |3 2 | 200 100 T 6 2 3 5 7 9 | | / | 3 | 200 200 T 3 1 2 3 4 -1 | +-+/ +-+ +============================================================+ *|1|-----|3|* +-+ 2 +-+ lastmade start dest perm state min minnode +=====+=====+========+=========+=======+=======+ 0 2 2 notneeded 6 2 ----------------------------------------------------------------------------------- 17. Stop when the destination node becomes permanent. Use the while loop while(lastmadeperm != dest) to control the iterations. Now trace the optimal path backwards from destination node 2 to 3 to 1 to 0. Stop when you get to the start node: // Set pen color, pen width, or pen style to something different for the // optimal path than what you are using to draw the edges. pnt = nodearray[dest].loc; index = dest; dc.MoveTo(pnt.x, pnt.y); while(index != start) { index = nodearray[index].prevnode; pnt = nodearray[index].loc; dc.LineTo(pnt.x, pnt.y); }