Dijkstra算法给定一个源点求解从源点到每个点的最短路径长度。单源最短路径算法。适用范围有向图、边的权值没有负数普通堆实现的Dijkstra算法最普遍、最常用a.节点弹出过就忽略b.节点没弹出过让其它没弹出节点距离变小的记录加入堆普通堆实现的Dijkstra算法时间复杂度o(m*1ogm)m为边数1distance[i]表示从源点到i点的最短距离visited[i]表示i节点是否从小根堆弹出过2准备好小根堆小根堆存放记录x点源点到x的距离小根堆根据距离组织3令distance[源点]0源点0)进入小根堆4从小根堆弹出u点源点到u的距离a.如果visited[u]true不做任何处理重复步骤4b.如果visited[u]false令visited[u]trueu就算弹出过了然后考察u的每一条边假设某边去往v边权为w1) 如果visited[v] false并且distance[u] w distance[v]令distance[v] distance[u] w把(vdistance[u] w)加入小根堆2处理完u的每一条边之后重复步骤45小根堆为空过程结束distance表记录了源点到每个节点的最短距离。