title: Heuristic algorithms to find the shortest path in a graph. Critique/improve my pseudo-code please
body: <p>I have to implement two heuristic algorithms that are described below. Both algorithms try to find a shortest path from a given input node to node Z using heuristic approaches. In a shortest path, a node may appear at most once (i.e., a node cannot appear twice or more in a shortest path, but backtracking is allowed). Note that these two heuristic algorithms do not always have to find a correct shortest path.</p>
  
  <p>Both algorithms should start with a given input node and iteratively determine the next node in a shortest path. In determining which node to choose as the next node, they use different heuristics.</p>
  
  <p>Let w(n, v) be the weight of the edge between node n and node v. Let dd(v) be the direct distance from v to the destination node Z.</p>
  
  <p>When choosing the next node from a current node n:</p>
  
  <p>Algorithm 1: Among all nodes v that are adjacent to the node n, choose the one with the smallest dd(v). </p>
  
  <p>Algorithm 2: Among all nodes v that are adjacent to the node n, choose the one for which w(n, v) + dd(v) is the smallest.</p>
  
  <p>Z is reachable by all nodes.
  All edge weights are positive integers.</p>
  
  <p>I've got the graph loaded correctly but have had trouble implementing the algorithms, so I scrapped everything and went back to the drawing board.</p>
  
  <p>Here is my pseudo-code, please let me know if I'm missing any cases or there is something else I need to consider. Efficiency is nice, but not necessary in this case. Any tip helps!</p>
  
  <pre><code>//----------    PSEUDOCODE ALGORITHM ONE   ----------//
  
      /*
      while currentNode != destination:
          add currentNode to visited list and set --&gt; list to track total path, set to track shortest path
          for each node adjacent to currentNode:
              if adjacentNode has minimum direct distance to destination:
                  get the connecting edge
                  nextNode = adjacentNode --&gt; nextNode = graph.opposite(currentNode, edgeToAdjacentNode)
                  if nextNode is not in visited: --&gt; list or set?
                      add edgeWeight to total distance traveled
                      add edgeWeight to shortest path distance
                      add nextNode to visited list and set
                      return find adjacentNode with minimum direct distance to destination (recurse on nextNode?)
                  else (nextNode has already been visited, we are backtracking):
                      get the connecting edge from currentNode to nextNode
                      add edgeWeight to total distance traveled
                      remove the edge connecting adjacentNode to nextNode --&gt; so we can't go back
                      remove key of nextNode from direct distance data structure --&gt; so it's no longer shortest
                      return find adjacentNode with minimum direct distance to destination (recurse on currentNode?)
      */
  
      //----------    END PSUEDOCODE ALGORITHM ONE    ----------//
  
      //----------    PSEUDOCODE ALGORITHM TWO    ----------//
  
      /*
      while currentNode != destination:
          add currentNode to visited list and set --&gt; list to track total path, set to track shortest path
          for each node adjacent to currentNode:
              calculate the sum of edgeWeight and direct distance to destination
          nextNode = adjacentNode with minimum sum
          if nextNode is not in visited (list or set?):
              add edgeWeight to total distance traveled
              add edgeWeight to shortest path distance
              add nextNode to visited list and set
              return recurse on nextNode?
          else:
              get the connecting edge from currentNode to nextNode
              add edgeWeight to total distance traveled
              remove the edge connecting adjacentNode to nextNode --&gt; so we can't go back
              remove key of nextNode from direct distance data structure --&gt; so it's no longer shortest
              return find adjacentNode with minimum direct distance to destination (recurse on currentNode?)
      */
  
      //----------    END PSUEDOCODE ALGORITHM TWO    ----------//
  </code></pre>
  
  <p>Output Example:</p>
  
  <p>(A)  User enters node J as the start node</p>
  
  <p>Algorithm 1: </p>
  
  <p>Sequence of all nodes: J -> K ->  Z
  Shortest path: J -> K ->  Z 
  Shortest path length: 310</p>
  
  <p>Algorithm 2:</p>
  
  <p>Sequence of all nodes: J -> I -> L -> Z
  Path: J -> I -> L -> Z 
  Length: 278</p>
  
  <p>(B) User enters node G as the start node</p>
  
  <p>Algorithm 1: </p>
  
  <p>Sequence of all nodes: G -> H -> T -> H -> L -> Z 
  Shortest path: G -> H -> L -> Z 
  Shortest path length: 359</p>
  
  <p>Algorithm 2:</p>
  
  <p>Sequence of all nodes: G -> H -> T -> H -> L -> Z
  Shortest path: G -> H -> L -> Z 
  Shortest path length: 359</p>