Dijkstras algorithm All In One

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

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*/

(🐞 反爬虫测试！打击盗版⚠️）如果你看到这个信息, 说明这是一篇剽窃的文章，请访问 https://www.cnblogs.com/xgqfrms/ 查看原创文章！

refs

https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/

https://medium.com/@alejandro.itoaramendia/a-guide-to-dijkstras-algorithm-all-you-need-99635dcd6d94

---

---

©xgqfrms 2012-2021

www.cnblogs.com/xgqfrms 发布文章使用：只允许注册用户才可以访问！

原创文章，版权所有©️xgqfrms, 禁止转载 🈲️，侵权必究⚠️！

---