Dijkstra's algorithm All In One
迪杰斯特拉
算法
Dijkstra
Dijkstra's algorithm (/ˈdaɪkstrəz/ DYKE-strəz) is an algorithm for finding the shortest paths
between nodes in a weighted graph
, which may represent, for example, road networks.
Dijkstra 算法是一种用于查找加权图
中节点之间最短路径
的算法,该算法可以表示例如道路网络
。
https://en.wikipedia.org/wiki/Dijkstra's_algorithm
https://zh.wikipedia.org/wiki/戴克斯特拉算法
https://en.wikipedia.org/wiki/Edsger_W._Dijkstra
demos
leetcode
https://leetcode.com/problems/path-with-maximum-probability
function maxProbability(n: number, edges: number[][], succProb: number[], start: number, end: number): number {
let map = {};
for (let i = 0; i < edges.length; i++) {
let [f, t] = edges[i];
if (map[f] === undefined) {
map[f] = {};
}
if (map[t] === undefined) {
map[t] = {};
}
map[f][t] = succProb[i];
map[t][f] = succProb[i];
}
if(map[end] === undefined) {
return 0;
}
let res = dijkstra(n, map, start, end);
return res;
};
// 迪克斯特拉
let dijkstra = (n: number, map: any, s: number, d: number) => {
let visited = new Array(n).fill(0);
let costs = new Array(n).fill(0);
costs[s] = 1;
while(true) {
let node;
for(let i=0; i<visited.length; i++) {
if(visited[i]) {
continue;
}
if(node === undefined) {
node = i;
} else {
node = costs[node] < costs[i] ? i: node;
}
}
if(node === undefined) {
break;
}
if(node === d) {
return costs[d];
}
visited[node] = 1;
if(map[node] === undefined) {
continue;
}
let adjNodes = Object.keys(map[node]);
for(let adj of adjNodes) {
if(visited[adj]) {
continue;
}
let w = map[node][adj] * costs[node];
costs[adj] = Math.max(costs[adj], w);
}
}
return costs[d];
}
"use strict";
/**
*
* @author xgqfrms
* @license MIT
* @copyright xgqfrms
* @created 2024-08-27
* @modified
*
* @description 1514. Path with Maximum Probability
* @description 1514. 概率最大的路径
* @difficulty Hard
* @ime_complexity O(n)
* @space_complexity O(n)
* @augments
* @example
* @link https://leetcode.com/problems/path-with-maximum-probability
* @link https://leetcode.cn/problems/path-with-maximum-probability
* @solutions
*
* @best_solutions
*
*/
export {};
const log = console.log;
function maxProbability(n: number, edges: number[][], succProb: number[], start: number, end: number): number {
let map = {};
for (let i = 0; i < edges.length; i++) {
let [f, t] = edges[i];
if (map[f] === undefined) {
map[f] = {};
}
if (map[t] === undefined) {
map[t] = {};
}
map[f][t] = succProb[i];
map[t][f] = succProb[i];
}
if(map[end] === undefined) {
return 0;
}
let res = dijkstra(n, map, start, end);
return res;
};
// 迪克斯特拉
let dijkstra = (n: number, map: any, s: number, d: number) => {
let visited = new Array(n).fill(0);
let costs = new Array(n).fill(0);
costs[s] = 1;
while(true) {
let node;
for(let i=0; i<visited.length; i++) {
if(visited[i]) {
continue;
}
if(node === undefined) {
node = i;
} else {
node = costs[node] < costs[i] ? i: node;
}
}
if(node === undefined) {
break;
}
if(node === d) {
return costs[d];
}
visited[node] = 1;
if(map[node] === undefined) {
continue;
}
let adjNodes = Object.keys(map[node]);
for(let adj of adjNodes) {
if(visited[adj]) {
continue;
}
let w = map[node][adj] * costs[node];
costs[adj] = Math.max(costs[adj], w);
}
}
return costs[d];
}
/*
undirected weighted graph
无向加权图
*/
/*
https://leetcode.com/problems/path-with-maximum-probability/description/?envType=daily-question&envId=2024-08-27
*/