Dijkstra’s algorithm pseudo code

Lecture 11: Dijkstra’s algorithm pseudo code Get input data Complete a path tree for each origin node by doing the following. Initialize the node table Step 1: Create the list of tentative node labels Update the node table Step 2: Finalize the current node Step 3: Find the next current node if there is a valid current node then Go to Step 1 otherwise, done Output the completed node table Main program for the assignment (green = comments; blue = name of subprocedure) ‘if the compute program has not read in the input data yet then tell it to go get it If have_input_data <> 1 Then get_nodes ‘get the nodes list get_links ‘get the link list ReDim node_table(num_nodes, 4) ReDim all_origins_node_table(num_nodes * num_zones, 5) 'this indicates whether or not we have done the node table for the first origin (0 means no) ‘knowing this will also tell us whether or not to set output counters to zero first_origin = 0 End If ‘know that we have all of the network input data we will not need to get the network input data any more. ‘This will help when using this code within the four step travel demand modeling framework. have_input_data = 1 'this will calculate costs depending on the link volumes assigned to the link calc_costs ‘This loop goes through each node in the list of nodes. As it finds zone nodes, it sets them up as the origin node and completes Dijkstra’s algorithm for them. For node_count = 1 To num_nodes ‘if this condition is true then the computer has found an origin node and a node table needs to be generated for it If nodes(node_count, 2) = "z" Then origin_zone = node_count 'the next zone was found. Set it as the origin node initialize_node_table debug_output ‘output the current node table and information for the list of tentative nodes origin_done = "no" ‘need to start working on the table for the origin node Do Until origin_done = "yes" find_neighboring_nodes 'Step one in Dijkstra's algorithm update_node_table 'Step one in Dijkstra's algorithm debug_output finalize_current_node 'Step two in Dijkstra's algorithm debug_output find_current_node 'Step three in Dijkstra's algorithm Loop ‘output the completed node table to the spreadsheet and to the array containing all of the node table for each of the origins. output_origin_node_table ‘when the computer reaches this point, it will have done the at least the first origin. ‘if it has only done the first origin then the first_origin variable would still be at zero. ‘if it is still zero then change the first_origin variable to 1 to say that the first origin has been ‘done. if first_origin = 0 then first_origin = 1 end if End If Next