Markov Chain: Find the most probable path from point A to point B

Question

I have a transition matrix using dictionary

{'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}}

which shows the probability of going from a certain hex to another hex (e.g. hex1 has probability 1 going to hex2, hex2 has probability 0.4 going to hex4).

Taking the starting and endpoint, I want to find the path that has the highest probability.

The structure of the code will look like

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

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.

Example would be

find_most_probable_path(hex2, hex3, 5)
>> "hex2,hex4,hex3"

The output can be a list of hexes or just concatenated strings.

Answer 1

I developed an algorithm but I have no idea about its efficiency but it works well.

table={'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}}

def find_most_probable_path(start_hex, end_hex, max_path=0):
    assigned=[start_hex]
    foundTrue=False
    prob=[{"nodes":[start_hex],"prob":1,"length":1}]
    if max_path==0:
        status=False
    else:
        status=True
    while status==True:
        chn=[]
        status=False
        for i in prob:
            if i["length"]<max_path:
                lastElement=i["nodes"][-1]
                for j in table[lastElement]:
                    if j not in assigned:
                        temp=i.copy()
                        js=temp["nodes"].copy()
                        js.append(j)
                        temp["nodes"]=js
                        temp["prob"]=temp["prob"]*table[lastElement][j]
                        temp["length"]+=1
                        #print(temp)
                        chn.append(temp)
                        status=True
        maxv=0
        for i in chn:
            if i["prob"]>=maxv:
                maxv=i["prob"]
                added=i
        if added["nodes"][-1]==end_hex:
            foundTrue=True
            status=False
        assigned.append(added["nodes"][-1])
        prob.append(added)
    if foundTrue==True:
        return prob[-1]["nodes"]
    else:
        return None


print(find_most_probable_path("hex2", "hex3",5))

The output will be:

['hex2', 'hex4', 'hex3']

If you want to see probability of path, you can change the part:

if foundTrue==True:
    return prob[-1]["nodes"]

to:

if foundTrue==True:
    return prob[-1]

Then the program give output like that:

{'nodes': ['hex2', 'hex4', 'hex3'], 'prob': 0.4, 'length': 3}

Answer 2

You can treat your Markov Chain as a directed weighted graph, and use the probabilities as graph edges weights.

From this point, you can use the Dijkstra algorithm for a shortest path from two points on a weighted graph.

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm