title: Markov Chain: Find the most probable path from point A to point B
body: <p>I have a transition matrix using dictionary</p>
  <pre class="lang-py prettyprint-override"><code>{'hex1': {'hex2': 1.0},
   'hex2': {'hex4': 0.4, 'hex7': 0.2, 'hex6': 0.2, 'hex1': 0.2},
   'hex4': {'hex3': 1.0},
   'hex3': {'hex6': 0.3333333333333333, 'hex2': 0.6666666666666666},
   'hex6': {'hex1': 0.3333333333333333,
    'hex4': 0.3333333333333333,
    'hex5': 0.3333333333333333},
   'hex7': {'hex6': 1.0},
   'hex5': {'hex3': 1.0}}
  </code></pre>
  <p>which shows the probability of going from a certain hex to another hex (e.g. <code>hex1</code> has probability 1 going to <code>hex2</code>, <code>hex2</code> has probability 0.4 going to <code>hex4</code>).</p>
  <p>Taking the starting and endpoint, I want to find the path that has the highest probability.</p>
  <p>The structure of the code will look like</p>
  <pre class="lang-py prettyprint-override"><code>def find_most_probable_path(start_hex, end_hex, max_path):
      path = compute for maximum probability path from start_hex to end_hex
      return path
  </code></pre>
  <p>where max_path is the maximum hexes to traverse. If there is no path within the max_path, return empty/null. Also, drop the path if goes back to the starting hex before reaching the ending hex.</p>
  <p>Example would be</p>
  <pre class="lang-py prettyprint-override"><code>find_most_probable_path(hex2, hex3, 5)
  &gt;&gt; &quot;hex2,hex4,hex3&quot;
  </code></pre>
  <p>The output can be a list of hexes or just concatenated strings.</p>