You are given an undirected weighted graph ofContinue reading “[Leetcode]1514. Path with Maximum Probability”n
nodes (0-indexed), represented by an edge list whereedges[i] = [a, b]
is an undirected edge connecting the nodesa
andb
with a probability of success of traversing that edgesuccProb[i]
. Given two nodesstart
andend
, find the path with the maximum probability of success to go fromstart
toend
and return its success probability. If there is no path fromstart
toend
, return 0. Example 1: Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2 Output: 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”