首页 > 其他分享 >Dijkstra's algorithm All In One

Dijkstra's algorithm All In One

时间:2024-08-27 23:26:01浏览次数:15  
标签:map algorithm number Dijkstra let https

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 算法是一种用于查找加权图中节点之间最短路径的算法,该算法可以表示例如道路网络

image

https://en.wikipedia.org/wiki/Dijkstra's_algorithm

https://zh.wikipedia.org/wiki/戴克斯特拉算法

image

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


*/

(

标签:map,algorithm,number,Dijkstra,let,https
From: https://www.cnblogs.com/xgqfrms/p/18383730

相关文章

  • 基于A*算法、Dijkstra算法的路径规划研究(Matlab代码实现)
      ......
  • Study Plan For Algorithms - Part11
    1.合并两个有序链表题目链接:https://leetcode.cn/problems/merge-two-sorted-lists/将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。classSolution:defmergeTwoLists(self,list1:Optional[ListNode],list2:Option......
  • SPFA && dijkstra 模版
    boolSPFA(ints){ intcnt=0; memset(dis,0x3f,sizeof(dis)); queue<int>q; q.push(s); vis[s]=1;dis[v]=0; while(!q.empty()) { intu=q.front();q.pop(); vis[u]=0; for(inti=0;i<g[u].size();i++) { intv=g[u][i].v,w=g[u][i].w; if(d......
  • Twenty Lectures on Algorithmic Game Theory 算法博弈论二十讲 Lecture 5 Revenue-Ma
    TwentyLecturesonAlgorithmicGameTheory算法博弈论二十讲Lecture5Revenue-MaximizingAuctions(上)Lecture5Revenue-MaximizingAuctions第2至第4讲聚焦于设计能够最大化社会福利的机制,无论是精确还是近似。这类机制的收益产生仅仅是副作用,是激励代理人如实......
  • Study Plan For Algorithms - Part8
    1.三数之和题目链接:https://leetcode.cn/problems/3sum/给定一个整数数组nums,判断是否存在三元组[nums[i],nums[j],nums[k]]满足i!=j、i!=k且j!=k,同时还满足nums[i]+nums[j]+nums[k]==0。返回所有和为0且不重复的三元组。classSolution:deft......
  • Dijkstra、Bellman_Ford、SPFA、Floyd算法复杂度比较
    说明Dijkstra:适用于权值为非负的图的单源最短路径,用斐波那契堆的复杂度O(E+VlgV)BellmanFord:适用于权值有负值的图的单源最短路径,并且能够检测负圈,复杂度O(VE)SPFA:适用于权值有负值,且没有负圈的图的单源最短路径,论文中的复杂度O(kE),k为每个节点进入Queue的次数,且k一般<=2,但此处......
  • Study Plan For Algorithms - Part7
    1.罗马数字转整数题目链接:https://leetcode.cn/problems/roman-to-integer/罗马数字包含以下七种字符:I,V,X,L,C,D和M。字符数值I1V5X10L50C100D500M1000通常情况下,罗马数字中小的数字在大的数字的右边。但也存在六种特例:I可以放在......
  • 最短路 - Dijkstra 算法
    Dijkstra(迪杰斯特拉)算法是基于贪心思想的单源最短路算法暴力Dijkstra具体如下:structnode{ intv,w;};vector<node>e[N];intdist[N],vis[N];e[u]存的是节点u的所有出边的终点和边权,dist[u]存u到原点s的最小距离,vis[u]标记是否走过voiddijkstra(int......
  • 《数据结构》最短路径Dijkstra算法
                                    最短路径Dijkstra算法分析生长点ABCDEFP(A)=FAD(A)=130P(B)=FBD(B)=24P(C)=FCD(C)=10P(D)=——D(D)=无穷P(E)=——D(E)=无穷CP(A)=FAD(A......
  • CHC5223 Data Structures and Algorithms
    CHC5223DataStructuresandAlgorithms2023-2024-21of6AssignmentValue100%ofCourseworkResitIndividualworkBackgroundThesubwaysystemofacityisanetworkofundergroundorelevatedtrainsthatproviderapidtransitforpassengerswithint......