用js简单实现一下迪克斯特拉算法

时间:2022-09-05 18:59:54

今天看书看到了迪克斯特拉算法,大概用js实现一下呢,计算最短路径。

首先,迪克斯特拉算法只适用于有向无环图,且没有负权重,本例关系图如下哦,数字为权重,emmmm,画得稍微有点丑~

用js简单实现一下迪克斯特拉算法

     //大概用js实现一下迪克斯特拉算法,计算最短路径
// (6)→ A → (1)
// ↑ ↑ ↓
// 起点 (3) 终点
// ↓ ↑ ↑
// (2) → B → (5)
//迪克斯特拉算法只适用于有向无环图,且没有负权重
//上图()内为权重
//散列表在js中表示为对象
var graph = {};//记录节点
graph.start = {};
graph.start.a = 6;//起点到达A点权重为6
graph.start.b = 2; graph.a = {};
graph.a.end = 1;
graph.b = {};
graph.b.end = 5;
graph.b.a = 3; graph.end = {}; var costs = {};//记录起点到各点权重
costs.a = 6;
costs.b = 2;
costs.end = '';//暂时不知道 var parents = {};//记录最短路径中各节点的父节点
parents.a = 'start';
parents.b = 'start';
parents.end = ''; var processed = {};//记录已处理过的节点 //找出开销最小的节点(方法比较多呢,随便写了一个)
function findLowestCostNode(costs) {
var value = '';
var node = '';
for(var key in costs) {
if(processed[key]) {
continue;
}
if(!value) {
value = costs[key];
node = key;
}else {
if(costs[key] && costs[key]<value) {
value = costs[key];
node = key;
}
}
}
return node;
} var node = findLowestCostNode(costs);//找出开销最小节点
while(node) {
var cost = costs[node];//当前最小开销
var neighbors = graph[node];//当前节点相邻节点
for(var n in neighbors) {
var newCost = cost + neighbors[n];//到达相邻节点的开销数
if (!costs[n]) {
costs[n] = newCost;
parents[n] = node;
}else {
if (costs[n] > newCost) {//检查相应节点开销数是否小于已知开销数
costs[n] = newCost;//更新相应节点开销数
parents[n] = node;//更新相应节点父节点
}
}
}
processed[node] = 1;;//记录已处理过节点
node = findLowestCostNode(costs);//更新最小节点继续循环
} console.log(costs['end']);//6 此处为最短路径开销
var line = [];
line.unshift('end');
printLine(parents['end']);
console.log(line);//["start", "b", "a", "end"] //使用递归打印出完整路径
function printLine(node) {
if( node != 'start') {
line.unshift(node);
printLine(parents[node]);
}else {
line.unshift('start');
}
}

看过的东西不使用就容易忘记,稍微记录一下,写法比较小白,大神们就自动忽略吧~

知道了新东西还真是一件有意思的事情~

用js简单实现一下迪克斯特拉算法的更多相关文章

  1. &lbrack;算法导论&rsqb;迪克斯特拉算法 &commat; Python

    class Graph: def __init__(self): self.V = [] self.w = {} class Vertex: def __init__(self, x): self.k ...

  2. Dijkstra Algorithm 迪克特斯拉算法--Python

    迪克斯拉特算法: 1.找出代价最小的节点,即可在最短时间内到达的节点: 2.更新节点的邻居的开销: 3.重复这个过程,直到图中的每个节点都这样做了: 4.计算最终路径. ''' 迪克斯特拉算法: 1. ...

  3. &lt&semi;经验杂谈&gt&semi;介绍Js简单的递归排列组合

    最近在开发SKU模块的时候,遇到这样一个需求,某种商品有N(用未知数N来表示是因为规格的数组由用户制定且随时可以编辑的,所以对程序来说,它是一个未知数)类规格,每一类规格又有M个规格值,各种规格值的组 ...

  4. 算法与数据结构&lpar;六&rpar; 迪杰斯特拉算法的最短路径&lpar;Swift版&rpar;

    上篇博客我们详细的介绍了两种经典的最小生成树的算法,本篇博客我们就来详细的讲一下最短路径的经典算法----迪杰斯特拉算法.首先我们先聊一下什么是最短路径,这个还是比较好理解的.比如我要从北京到济南,而 ...

  5. c&sol;c&plus;&plus; 图的最短路径 Dijkstra&lpar;迪杰斯特拉&rpar;算法

    c/c++ 图的最短路径 Dijkstra(迪杰斯特拉)算法 图的最短路径的概念: 一位旅客要从城市A到城市B,他希望选择一条途中中转次数最少的路线.假设途中每一站都需要换车,则这个问题反映到图上就是 ...

  6. 单源最短路径-迪杰斯特拉算法(Dijkstra&&num;39&semi;s algorithm)

    Dijkstra's algorithm 迪杰斯特拉算法是目前已知的解决单源最短路径问题的最快算法. 单源(single source)最短路径,就是从一个源点出发,考察它到任意顶点所经过的边的权重之 ...

  7. JS实现最短路径之弗洛伊德&lpar;Floyd&rpar;算法

    弗洛伊德算法是实现最小生成树的一个很精妙的算法,也是求所有顶点至所有顶点的最短路径问题的不二之选.时间复杂度为O(n3),n为顶点数. 精妙之处在于:一个二重初始化,加一个三重循环权值修正,完成了所有 ...

  8. Java 迪杰斯特拉算法实现查找最短距离

    迪杰斯特拉算法 迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法.是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题.迪杰斯特拉算法主要特点是 ...

  9. JS简单实现:根据奖品权重计算中奖概率实现抽奖的方法

    本文主要介绍:使用 JS 根据奖品权重计算中奖概率实现抽奖的方法. 一.示例场景 1.1.设置抽奖活动的奖项名称 奖项名称:["一等奖", "二等奖", &qu ...

随机推荐

  1. win8安装SQL Server2008企业版

    win8 系统,安装的时候要先安装SQL Server2008企业版 再安装Visual studio2010,不然SQL Server会有问题.

  2. jsp--- jsp图片上传到了正确路径,但在正确路径显示不出来

    首先要说的是,路径里没有中文 图片也在正确路径 ************************************ 刷新(Refresh)一下项目

  3. 【leetcode】Candy(hard&rpar; 自己做出来了 但别人的更好

    There are N children standing in a line. Each child is assigned a rating value. You are giving candi ...

  4. cpp&lpar;第四章&rpar;

    1.索引比数组长度少1: 2.c++中不能数组赋给另一个数组:只能定义时才能使用初始化: 3.c++11中{}内为空,默认赋值为0,而c++中{}如果只对部分初始化,其他部分将被设置为0:c++11使 ...

  5. MS SQL CASE WHEN 的用法

    前言 由于经常使用 case when 的2种情况方式,如果=1 则*** 否则 *** 结束.久而久之,都以为只能这么用,都忘记了Case WHEN 的用法. 示例   ,              ...

  6. &lbrack;macOS&rsqb; PHP双版本,5&period;6跟7&period;1

    转过来的,原文看这里,https://www.symfony.fi/page/how-to-run-both-php-5-6-and-php-7-x-with-homebrew-on-os-x-wit ...

  7. JDK安装与配置(Windows 7系统)

    1.前言 安装之前需弄清JDK.JRE.JVM这几个概念,不然稀里糊涂不知道自己在装什么. (1)什么是java环境:我们知道,想听音乐就要安装音乐播放器,想看图片需要安装图片浏览器,同样道理,要运行 ...

  8. 2018&period;9&period;25 NOIP模拟赛

    *注意:这套题目应版权方要求,不得公示题面. 从这里开始 Problem A XOR Problem B GCD Problem C SEG 表示十分怀疑出题人水平,C题数据和标程都是错的.有原题,差 ...

  9. Linux命令之ll

    ll命令 用处:以长格形式列出当前目录下的所有文件,每个文件的长度和创建时间不同. 用法:输入 ll 示例: 前面的一大串字母的意思,第一个要么是d要么是-,d的意思就是目录,-的意思就是文件.其后的 ...

  10. Android Bander设计与实现 - 设计

    Binder Android IPC Linux 内核 驱动 摘要 Binder是Android系统进程间通信(IPC)方式之一.Linux已经拥有管道,system V IPC,socket等IPC ...