title: 2D array (board) shortest path with highest score
body: <p>I am developing a new game with an 2D array (game board). Each cell/ tile has a amount of points.</p>
  
  <p><img src="https://i.stack.imgur.com/kuxZC.png" alt="enter image description here"></p>
  
  <p>What I want to achieve is that an algorithm can find the shortest path with the highest core.</p>
  
  <p>So I first implemented the Dijkstra Algorithm (source code below) to find the shortest path from start to end (red route). This works great.</p>
  
  <p>My question is: How can I extend my algorithm, so it determines the shortest path with the <strong>highest</strong> score (so the green route).</p>
  
  <p>Thank you in advance!</p>
  
  <pre><code>class Graph
  {
      // Dictionary&lt;Start Point, vertices&gt;
      Dictionary&lt;char, Dictionary&lt;char, int&gt;&gt; vertices = new Dictionary&lt;char, Dictionary&lt;char, int&gt;&gt;();
  
      public void add_vertex(char name, Dictionary&lt;char, int&gt; edges)
      {
          vertices[name] = edges;
      }
  
      public List&lt;char&gt; shortest_path(char start, char finish)
      {
          var previous = new Dictionary&lt;char, char&gt;();
          var distances = new Dictionary&lt;char, int&gt;();
          var nodes = new List&lt;char&gt;();
  
          List&lt;char&gt; path = null;
  
          foreach (var vertex in vertices)
          {
              if (vertex.Key == start)
              {
                  distances[vertex.Key] = 0;
              }
              else
              {
                  distances[vertex.Key] = int.MaxValue;
              }
  
              nodes.Add(vertex.Key);
          }
  
          while (nodes.Count != 0)
          {
              nodes.Sort((x, y) =&gt; distances[x] - distances[y]);
  
              var smallest = nodes[0];
              nodes.Remove(smallest);
  
              if (smallest == finish)
              {
                  path = new List&lt;char&gt;();
                  while (previous.ContainsKey(smallest))
                  {
                      path.Add(smallest);
                      smallest = previous[smallest];
                  }
  
                  break;
              }
  
              if (distances[smallest] == int.MaxValue)
              {
                  break;
              }
  
              foreach (var neighbor in vertices[smallest])
              {
                  var alt = distances[smallest] + neighbor.Value;
                  if (alt &lt; distances[neighbor.Key])
                  {
                      distances[neighbor.Key] = alt;
                      previous[neighbor.Key] = smallest;
                  }
              }
          }
  
          return path;
      }
  }
  </code></pre>
  
  <p><strong>Update:</strong></p>
  
  <p>I already tried something like this, but doesn't seem to work:</p>
  
  <pre><code>  foreach (var neighbour in _vertices[smallest])
    {
        // The variable alt is the length of the path from the root node to the neighbor node if it were to go through _vertices[smallest].
        var alt = pointInfos[smallest].Distance + neighbour.Value.Distance;
        var altScore = pointInfos[smallest].Points + neighbour.Value.Points;
        if (alt &lt;= pointInfos[neighbour.Key].Distance &amp;&amp; altScore &gt; pointInfos[neighbour.Key].Points) // A shorter path with higher points to neighbour has been found
        {
            pointInfos[neighbour.Key] = new PointInfo(alt, altScore);
            previous[neighbour.Key] = smallest;
        }
    }
  </code></pre>