I will introduce how to find the shortest path on the graph where the travel time changes stochastically.

Make a sample graph.

python3

%matplotlib inline
import numpy as np, networkx as nx

m = 4
g = nx.Graph()
for i in range(m):
    if i==0:
        g.add_edge(i, i+m, prob=[1], time=[1.9]) # 0-> 4
    else:
        g.add_edge(i, i+m, prob=[0.8, 0.2], time=[1, 6]) #Vertical
    if i < m-1:
        g.add_edge(i, i+1, prob=[1], time=[2]) #side
        g.add_edge(i+m, i+m+1, prob=[1], time=[2]) #side

n = g.number_of_nodes()
pos = {i:[i%m, i//m] for i in range(n)}
nx.draw_networkx_nodes(g, pos, node_color='w')
nx.draw_networkx_edges(g, pos)
nx.draw_networkx_labels(g, pos, {i:str(i) for i in range(n)});

--Find the shortest path ** from point 0 to point 7 above. ――The side road definitely takes 2 hours. ――The vertical road has a probability of 80% and takes 1 hour, but with a probability of 20% it takes 6 hours. It takes 2 hours on average. ――From point 0 to point 4, you can definitely go in 1.9 hours. ――When you reach a certain point, only the movement time of the side connected to that point shall be fixed.

In terms of average time, the route is "0-> 4-> 5-> 6-> 7", and 7.9 hours is the shortest route.

However, on a vertical road, you can go from bottom to top with an 80% chance of going in an hour. From this, it seems good to go up if you go vertically in 1 hour while going to the right.

Invented Monte Carlo Dijkstra method

――Prepare nn random numbers for each side determined by probability in advance. --Set the time to reach the end point to ∞ at all points, and leave all points unsearched. --Set the next point as the end point, and set the arrival time of the next point to 0. --Repeat the following until the starting point has been searched. --Mark the following points as searched. --Update the arrival time of the point connecting to the next point as described below. --Among the points that have not been searched, the one with the shortest arrival time is set as the next point.

Reach time update

--Update if the average of nn times of the sample values below is shorter than the current arrival time. --For the point to connect the sample value, set it to the minimum value of "sum of arrival time and connection side time".

Try to calculate

python3

def monte_min(g, s, t, nn=1000):
    n = g.number_of_nodes()
    dd = [np.inf] * n
    bb = [False] * n
    for i, j in g.edges():
        d = g.edge[i][j]
        d['log'] = (np.random.multinomial(1, d['prob'], nn) * d['time']).sum(axis=1)
    nx = t
    dd[nx] = 0
    while not bb[s]:
        bb[nx] = True
        for nd in g.edge[nx].keys():
            dd[nd] = min(dd[nd], np.mean([calcmin(dd, g.edge[nd], i) for i in range(nn)]))
        nx = np.argmin([np.inf if bb[i] else dd[i] for i in range(n)])
        if dd[nx] == np.inf: break
    return dd
def calcmin(dd, dc, i):
    return min([dd[nd] + d['log'][i] for nd, d in dc.items()])

print(monte_min(g, 0, 7))
>>>
[7.0436741200000021,
 5.0366892306401603,
 3.1682992231199996,
 1.7938642600000001,
 6.0,
 4.0,
 2.0,
 0]

Output the arrival time for each point with monte_min.

The average Dijkstra was 7.9, but when calculated in Monte Carlo it was 7.04. Also, if you pass through point 4, it will be 7.9 (= 6.0 + 1.9), but if you go through point 1, it will be 7.04 (= 5.04 + 2), so it is better to go from point 0 to point 1.

When you reach point 1, go to point 2 and you get 5.17 (= 3.17 + 2). At this time, if the side (1-5) is 1, it becomes 5 (= 4.0 + 1), and if the side (1-5) is 6, it becomes 10 (= 4.0 + 6). As you can see, it is better to go up when the up travel time is 1.

Note that this Monte Carlo Dijkstra method does not guarantee an exact optimal solution even if the sampling is accurate.

that's all