单源最短路径算法——迪杰斯特拉算法

算法思想

迪杰斯特拉属于贪心算法，将顶点分为已确定最短路径的顶点集合V和未确定最短路径的顶点集合U。初始条件下，只有源点在集合V中，其他所有顶点在集合U中。每次迭代时，选择离源点最近的顶点加入集合V，并作为中心进行扩展，更新其相邻边的路径长。

JavaScript代码

const INF=Number.MAX_SAFE_INTEGER;

const minDistance=(dist, visited)=>{
  var min=INF;
  var minIndex=-1;
  for(let u=0; u<dist.length; u++){
    //选择未确定最短路径的节点
    if(visited[u]==false && dist[u]<min){
      min=dist[u];
      minIndex=u;
    }
  }
  return minIndex;
}

const dijkstra=(graph, src)=>{
  const dist=[];
  const visited=[];
  const {length} = graph; //节点数
  for(let i=0; i<length; i++){
    dist[i]=INF;//初始化为不可达
    visited[i]=false;//开始都未访问过
  }
  dist[src]=0;
  for(let i=0; i<length; i++){
    const v=minDistance(dist, visited);
    visited[v]=true;
    for(let u=0; u<length; u++){
      if(!visited[u]&&
          dist[v]!=INF&&
          graph[v][u]!=0&&
          dist[v]+graph[v][u]<dist[u]){
            dist[u]=dist[v]+graph[v][u];
        }
    }
  }

  return dist;
}

var graph=[
    [0,2,4,0,0,0],
    [0,0,2,4,2,0],
    [0,0,0,0,3,0],
    [0,0,0,0,0,2],
    [0,0,0,3,0,2],
    [0,0,0,0,0,0]
];

var dist=dijkstra(graph, 0);
console.log(dist);

推荐链接

[坐在马桶上学算法: Dijkstra最短路算法]（https://wiki.jikexueyuan.com/project/easy-learn-algorithm/dijkstra.html）