Bellman-Ford算法
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 findSourceNode(graph,node,start){ let arr = [] for(let i in graph){ if(i===start){ continue } for(let j in graph[i]){ if(graph[i][j]['target']===node){ arr.push({startNode:i,value:graph[i][j]['value']}) } } } return arr } let graph = { a:[{target:'b',value:6},{target:'c',value:5},{target:'d',value:5}], b:[{target:'e',value:-1}], c:[{target:'b',value:-2},{target:'e',value:1}], d:[{target:'c',value:-2},{target:'f',value:-1}], e:[{target:'g',value:3}], f:[{target:'g',value:3}], g:[] } //图数据 graph = { a:[{target:'b',value:-1},{target:'c',value:4}], b:[{target:'c',value:3},{target:'e',value:2},{target:'d',value:-2}], c:[], d:[{target:'b',value:1}], e:[{target:'d',value:-3}], } //图数据 let start = 'a' //起点位置 let cost = getCostByPositiveGraph (graph,start) let parent = getParentNode (graph,start) let graphNodeNum = 0//节点总数 for(let i in graph){ graphNodeNum++ } let nodeCostTotalStr = '' //所有node消费总额 let stepList = [] for(let i = 1 ;i<graphNodeNum;i++){ for(let j in cost){ let list = findSourceNode(graph,j,start) for(let k in list){ let startNode = list[k].startNode let value = list[k].value if((cost[startNode]+value)<cost[j]) { cost[j]=cost[startNode]+value parent[j]=startNode } } } nodeCostTotalStr = '' for(let node in cost){//每次循环的花费总额保存进list中 let value = '0' if(cost[node]!==Infinity){ value = cost[node] } nodeCostTotalStr = nodeCostTotalStr + value.toString() } stepList.push(nodeCostTotalStr) console.log(stepList) if((stepList[i-1]===stepList[i-2])&&i!==1){//循环过程中出现重复的cost表 ==> 即cost表不再更新 ==> 结束循环并得出结果 break; }else{//负权环判断 ==> 循环次数已经超过V-1 但仍有更新cost表 if(i===graphNodeNum-1){ console.log('无解，因为存在负权环') break; } } } console.log(cost,parent)