Dijkstra算法
function getCostByPositiveGraph (graph,start) { let cost = {} for(let i in graph){ for (let j in graph[start]){ if(i === graph[start][j]['target']){ cost[i] = graph[start][j]['value'] break }else{ cost[i] = Infinity } } } delete cost[start] return cost } function getParentNode (graph,start) { let parent = {} for(let i in graph){ for (let j in graph[start]){ if(i===graph[start][j]['target']){ parent[i]=start break; }else{ parent[i]='unknown' } } } delete parent[start] return parent } function findLowestcostNode (cost,checked) { let lowest = Infinity let lowestNode = null for(let i in cost){ if(cost[i]<lowest){ let flag = true for(let j=0;j<checked.length;j++){ if(checked[j] === i) { flag = false break } } if(flag){ lowest = cost[i] lowestNode = i } } } return lowestNode } let graph = { a:[{target:'b',value:5},{target:'c',value:2}], b:[{target:'d',value:4},{target:'e',value:2}], c:[{target:'b',value:8},{target:'e',value:7}], d:[{target:'f',value:3},{target:'e',value:6}], e:[{target:'f',value:1}], f:[] } //图数据 let start = 'a' let cost = getCostByPositiveGraph (graph,start) //花销表 let parent = getParentNode (graph,start) //父节点表 let checked = [] //完检节点表 ==> 用来判断环并退出对环的检查 let nodeNum = 0 for(let i in graph){ nodeNum++ } //循环图 //需要循环所有的点，所以循环次数为V（V是node总数），因为cost表默认已循环第一个点源点，所以这里循环总次数为V-1=5，V=6 for(let j = 1; j<nodeNum;j++){ lowestNode = findLowestcostNode (cost,checked) if(!lowestNode){ console.log('error') break; } for(let i in graph[lowestNode]){ let nextTarget = graph[lowestNode][i]['target'] let nextTargetValue = graph[lowestNode][i]['value'] let totalCost = cost[lowestNode]+nextTargetValue if(totalCost<cost[nextTarget]){ cost[nextTarget] = totalCost parent[nextTarget] = lowestNode } } checked.push(lowestNode) } console.log(cost,parent,checked) ``