js迪杰斯特拉算法求最短路径

2024-06-19 21:08

本文主要是介绍js迪杰斯特拉算法求最短路径,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 

1.后台生成矩阵

名词解释和下图参考:https://blog.csdn.net/csdnxcn/article/details/80057574

814286-20181012093809324-1159397656.png

 

double[,] arr = new double[allVertices.Count(), allVertices.Count()]; //矩阵 

//allVertices所有三维坐标点的集合

814286-20181012094047352-1734830214.png

//lines 所有两点的连线

814286-20181012094201515-169113443.png

 

 

for (int i = 0; i < allVertices.Count(); i++)
{
for (int j = 0; j < allVertices.Count(); j++)
{
var start1 = allVertices[i].Point; //起点
var end1 = allVertices[j].Point; //终点
//lines 两点的连线集合
var line = lines.FirstOrDefault(ee => (ee.StartPoint == start1 && ee.EndPoint == end1)|| (ee.StartPoint == end1 && ee.EndPoint == start1/*起点终点互换*/));
if (start1 == end1)
{//同一个点
arr[i, j] = 0;
}
else
{
if (line != null)
{
arr[i, j] = double.Parse(line.Remark); //长度
}
else
{//两点未连接 此路不通
arr[i, j] =1.0/0.0; //Infinity
}
}
}
}

return arr;

2.dijkstra算法

/**
* Dijkstra算法
*
* @author wupanpan@baidu.com
* @date 2014-03-26
*/

/**
* @const
*/
var POS_INFINITY = Infinity;

/**
* @param {number} sourceV 源点的索引,从0开始
* @param {Array} adjMatrix 图的邻接矩阵,是一个二维数组
*/

function dijkstra(sourceV, adjMatrix) {
var set = [],
path = [],

dist = [];
distCopy = [],
vertexNum = adjMatrix.length;

var temp, u,
count = 0;

// 初始化
for (var i = 0; i < vertexNum; i++) {
distCopy[i] = dist[i] = POS_INFINITY;
set[i] = false;
}
distCopy[sourceV] = dist[sourceV] = 0;

while (count < vertexNum) {
u = distCopy.indexOf(Math.min.apply(Math, distCopy));
set[u] = true;
distCopy[u] = POS_INFINITY;

for (var i = 0; i < vertexNum; i++) {
if (!set[i] && ((temp = dist[u] + adjMatrix[u][i]) < dist[i])) {
distCopy[i] = dist[i] = temp;
path[i] = u;
}
}
count++;
}

return {
path: path,
dist: dist
};
}

/**
* @param {number} v 源点索引, 从0开始
* @param {number} d 非源点索引, 从0开始
* @param {Array} adjMatrix 图的邻接矩阵,是一个二维数组
*/
function searchPath(v, d, adjMatrix) {
var graph = dijkstra(v, adjMatrix),
path = graph.path,
dist = graph.dist;

var prev = path[d],
queue = [],
str = '';

queue.push(d);
while(prev != v) {
queue.push(prev);
prev = path[prev];
}
queue.push(v);

for (var j = queue.length - 1; j >= 0; j--) {
str +=queue.pop() + '->';
}
console.log('path',str);
var arr=str.split('->');
if(str.endsWith('->')){
arr.pop();
}
var rarr=[];//字符串数组转int数组
for(var i=0;i<arr.length;i++){
rarr.push(parseInt(arr[i]));
}
return rarr;
}


/**
* 测试数据
*/
var adjM = [
[0, 4, 2, POS_INFINITY, POS_INFINITY, POS_INFINITY],
[4, 0, 1, 5, POS_INFINITY, POS_INFINITY],
[2, 1, 0, 8, 10, POS_INFINITY],
[POS_INFINITY, 5, 8, 0, 2, 6],
[POS_INFINITY, POS_INFINITY, 10, 2, 0, 3],
[POS_INFINITY, POS_INFINITY, POS_INFINITY, 6, 3, 0]
];

3.使用算法求最短路径

814286-20181012091958954-657687797.png

 

5个点坐标如上图 虚线表示两点相连

1:  0,0,0
2:  1,1,0
3:  -1,-1,0
4:  2,0,0
5:  0,-1,0

 

请求后台生成的矩阵为:

var pathMatrix = [
[
0,
1.73,
1.73,
"Infinity",
1
],
[
1.73,
0,
"Infinity",
1.73,
"Infinity"
],
[
1.73,
"Infinity",
0,
"Infinity",
"Infinity"
],
[
"Infinity",
1.73,
"Infinity",
0,
2.23
],
[
1,
"Infinity",
"Infinity",
2.23,
0
]
];

var ret = searchPath(4, 1, pathMatrix); //从第5点到第2点的最短路径
console.log('index', ret);

 814286-20181012091722447-751725031.png(索引从0开始,对应到图上是 5->1->2)

 4.使用threejs画出路径

(黑色连线;  红绿蓝为xyz辅助线)

814286-20181012092523313-1086862149.png

 

geometryPoint = new THREE.BoxGeometry(0.2, 0.2, 0.2);
var materialPoint = new THREE.MeshBasicMaterial({
color: 0xff00ff,
side: THREE.DoubleSide
});
circlePoint1 = new THREE.Mesh(geometryPoint, materialPoint);
circlePoint1.position.set(0, 0, 0);
scene.add(circlePoint1);

circlePoint2 = circlePoint1.clone();
circlePoint2.position.set(1, 1, 0);
scene.add(circlePoint2);

circlePoint3 = circlePoint1.clone();
circlePoint3.position.set(-1, 1, 0);
scene.add(circlePoint3);


circlePoint4 = circlePoint1.clone();
circlePoint4.position.set(2, 0, 0);
scene.add(circlePoint4);


circlePoint5 = circlePoint1.clone();
circlePoint5.position.set(0, -1, 0);
scene.add(circlePoint5);

scene.add(new THREE.AxesHelper(300));

//画路径

var ret = searchPath(4, 1, pathMatrix);   //从第5点到第2点的最短路径
console.log('index', ret);

var geometry1 = new THREE.Geometry();
for (var i = 0; i < ret.length; i++) {
console.log("circlePoint" + (ret[i] + 1));
var pointObj = eval("circlePoint" + (ret[i] + 1));
console.log('position', pointObj.position);
geometry1.vertices.push(pointObj.position);
}
var line = new THREE.Line(geometry1, new THREE.LineBasicMaterial({
color: 'black'
}), THREE.LinePieces);
scene.add(line);

 

//补充

//threejs求三维两点的距离

var distance = circlePoint4.position.distanceTo(circlePoint5.position);
console.log(distance);

 

From:https://www.cnblogs.com/xuejianxiyang/p/9776319.html

这篇关于js迪杰斯特拉算法求最短路径的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1076154

相关文章

JS+HTML实现在线图片水印添加工具

《JS+HTML实现在线图片水印添加工具》在社交媒体和内容创作日益频繁的今天,如何保护原创内容、展示品牌身份成了一个不得不面对的问题,本文将实现一个完全基于HTML+CSS构建的现代化图片水印在线工具... 目录概述功能亮点使用方法技术解析延伸思考运行效果项目源码下载总结概述在社交媒体和内容创作日益频繁的

Node.js 数据库 CRUD 项目示例详解(完美解决方案)

《Node.js数据库CRUD项目示例详解(完美解决方案)》:本文主要介绍Node.js数据库CRUD项目示例详解(完美解决方案),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考... 目录项目结构1. 初始化项目2. 配置数据库连接 (config/db.js)3. 创建模型 (models/

使用Node.js制作图片上传服务的详细教程

《使用Node.js制作图片上传服务的详细教程》在现代Web应用开发中,图片上传是一项常见且重要的功能,借助Node.js强大的生态系统,我们可以轻松搭建高效的图片上传服务,本文将深入探讨如何使用No... 目录准备工作搭建 Express 服务器配置 multer 进行图片上传处理图片上传请求完整代码示例

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

用js控制视频播放进度基本示例代码

《用js控制视频播放进度基本示例代码》写前端的时候,很多的时候是需要支持要网页视频播放的功能,下面这篇文章主要给大家介绍了关于用js控制视频播放进度的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言html部分:JavaScript部分:注意:总结前言在javascript中控制视频播放

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想