You are given an undirected weighted graph ofContinue reading “[Leetcode]1514. Path with Maximum Probability”`n`

nodes (0-indexed), represented by an edge list where`edges[i] = [a, b]`

is an undirected edge connecting the nodes`a`

and`b`

with a probability of success of traversing that edge`succProb[i]`

. Given two nodes`start`

and`end`

, find the path with the maximum probability of success to go from`start`

to`end`

and return its success probability. If there is no path from`start`

to`end`

,return 0.Example 1:Input:n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2Output:0.25000

## Shortest Path Algorithms I – Dijkstra

The shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized. (Wikipedia) In this and coming posts some of the most common algorithms to solve the shortest path problems will be explained. Today’s topic is Dijkstra.

Continue reading “Shortest Path Algorithms I – Dijkstra”