首页 > 代码库 > javascript实现有向无环图中任意两点最短路径的dijistra算法
javascript实现有向无环图中任意两点最短路径的dijistra算法
有向无环图
一个无环的有向图称做有向无环图（directed acycline praph）。简称DAG 图。DAG 图是一类较有向树更一般的特殊有向图，
dijistra算法
摘自 http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html
1.定义概览
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。
问题描述：在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短路径。（单源最短路径）
javascript实现
<html><body><script>//有向无环图var pages = []//开始结点有两个后继pages["welecome"] = [];pages["welecome"]["nextNode"] = [];pages["welecome"]["nextNode"][0] = "workmode"//一个后继又有两个后继pages["workmode"] = [];pages["workmode"]["nextNode"] = [];pages["workmode"]["nextNode"][0] = "WAN"pages["workmode"]["nextNode"][1] = "WLAN"//WAN的后继为WLANpages["WAN"] = [];pages["WAN"]["nextNode"] = [];pages["WAN"]["nextNode"][0] = "WLAN"//WLAN的后继为终点pages["WLAN"] = [];pages["WLAN"]["nextNode"] = [];pages["WLAN"]["nextNode"][0] = "OVER"//终点pages["OVER"] = [];pages["OVER"]["nextNode"] = [];/* 计算有向无环图中，指定两点之间的最短路径 */function ComputeShortPath(map, startName, endName){ //判断两个节点是否有前后继关系，第一个为前，后一个为后 function IsSuccessor(nodeNameA, nodeNameB) { var page = pages[nodeNameA]; var nextNodes = page["nextNode"]; for ( var index in nextNodes ) { var nextNode = nextNodes[index]; if ( nextNode == nodeNameB ) { return true; } } return false; } /* 生成权重矩阵 */ function GenerateEdgeWeight(map) { document.write("---- Generate edgeWeightMatrix ----</br>") /* 记录图中各个点之间有向边的权重 */ var edgeWeightMatrix = []; for ( var nodeNameA in map ) { edgeWeightMatrix[nodeNameA] = []; for ( var nodeNameB in map ) { var isSucc = IsSuccessor(nodeNameA, nodeNameB); var weight; if ( true == isSucc ) { /* 有前后继的关系，权重设置为1 */ weight = 1; } else { /* 没有前后继的关系，权重设置为正无穷 */ weight = Number.POSITIVE_INFINITY; } edgeWeightMatrix[nodeNameA][nodeNameB] = weight; document.write("edgeWeightMatrix["+nodeNameA+"]["+nodeNameB+"]="+edgeWeightMatrix[nodeNameA][nodeNameB]+"</br>") } } return edgeWeightMatrix; } /* 产生Dijistra运算的数据结构 */ function GenerateDijistraDataStruct(map, startName, edgeWeightMatrix) { var dijistraJSON = { /* 已经知道最短路径集合 */ knownSet:[], /* 未知最短路径集合 */ unKnownSet:[], /* 最短特殊路径长度 */ distanceSP:[], }; /* 初始化，出发点添加到已知集合，其他添加到未知集合 */ for ( var nodeName in map ) { if ( nodeName == startName ) { dijistraJSON.knownSet.push(startName); } else { dijistraJSON.unKnownSet.push(nodeName); } } /* 初始化最短特殊路径 */ document.write("---- Generate distanceSP with startName = "+startName+" ----</br>") for ( var index in dijistraJSON.unKnownSet ) { var nodeName = dijistraJSON.unKnownSet[index]; dijistraJSON.distanceSP[nodeName] = edgeWeightMatrix[startName][nodeName]; document.write("distanceSP["+nodeName+"]="+dijistraJSON.distanceSP[nodeName]+"</br>"); } return dijistraJSON; } /* 运行最短路计算逻辑 */ function DoDijistraComputing(dijistraJSON, edgeWeightMatrix) { /* dijstra */ var loopNum = dijistraJSON.unKnownSet.length; for ( var i=0; i<loopNum; i++ ) { /* 找unKnownSet中最短特殊路径顶点 */ var minDistName = dijistraJSON.unKnownSet[0]; var minDistIndex = 0; var minDist = dijistraJSON.distanceSP[minDistName]; for ( var index in dijistraJSON.unKnownSet ) { var nodeName = dijistraJSON.unKnownSet[index]; var dist = dijistraJSON.distanceSP[nodeName]; if ( dist < minDist ) { minDist = dist; minDistName = nodeName; minDistIndex = index; } } /* 将最短特殊路径顶点，从unkownSet中删除，加入knownSet */ dijistraJSON.unKnownSet.splice(minDistIndex, 1); dijistraJSON.knownSet.push(minDistName); /* 更新 unKnownSet 中元素的 distanceSP 值 */ for ( var index in dijistraJSON.unKnownSet ) { var nodeName = dijistraJSON.unKnownSet[index]; var oldDist = dijistraJSON.distanceSP[nodeName]; var weight = edgeWeightMatrix[minDistName][nodeName]; var newDist = minDist + weight; if ( newDist < oldDist ) { dijistraJSON.distanceSP[nodeName] = newDist; } } } /* 输出看打印结果 */ document.write("---- Complete distanceSP with startName = "+startName+" ----</br>") for ( var index in dijistraJSON.knownSet ) { var nodeName = dijistraJSON.knownSet[index]; document.write("distanceSP["+nodeName+"]="+dijistraJSON.distanceSP[nodeName]+"<br/>"); } return dijistraJSON; } /* 获取最短路径 */ function GetShortPath(dijistraJSON, endName) { return dijistraJSON.distanceSP[endName]; } var edgeWeightMatrix = GenerateEdgeWeight(map); var dijistraJSON = GenerateDijistraDataStruct(map, startName, edgeWeightMatrix); dijistraJSON = DoDijistraComputing(dijistraJSON, edgeWeightMatrix); var shortPath = GetShortPath(dijistraJSON, endName); document.write("---- Complete shortpath between "+startName+" and "+endName+" = "+shortPath+"----</br>")}ComputeShortPath(pages, "welecome", "OVER");</script></body></html>
计算结果截图：
最后计算结果， 中distanceSP中每一个定点的值，都是开始结点 welecome到此结点的 最短距离。
javascript实现有向无环图中任意两点最短路径的dijistra算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。