// Dijkstra implements the dijkstra shortest path algorithm
Dijkstra implements the dijkstra shortest path algorithm
// Dijkstra implements the dijkstra shortest path algorithm
func Dijkstra(g *weightedgraph.WeightedGraph, s graph.NodeID) *ShortestPaths {
	sp := &ShortestPaths{}
	sp.initializeSingleSource(g, s)
	h := queryHeap{priorityQueue{}, map[graph.NodeID]*pqItem{}}
	g.IterateAllNodes(func(u graph.NodeID) {
		item := &pqItem{u, sp.nodesMap[u].d, h.Len()}
		h.priorityQueue = append(h.priorityQueue, item)
		h.m[u] = item
	})
	heap.Init(&h.priorityQueue)
	for h.Len() > 0 {
		u := sp.extractMin(&h)
		g.IterateAdjacencyNodes(u, func(v graph.NodeID) {
			w, _ := g.Weight(u, v)
			newWeight := sp.relax(u, v, w)
			if newWeight > 0 {
				if vItem, ok := h.m[v]; ok {
					vItem.priority = newWeight
					heap.Fix(&h.priorityQueue, vItem.index)
				}
			}
		})
	}
	return sp
}
func Dijkstra ( g * weightedgraph . WeightedGraph , s graph . NodeID ) * ShortestPaths { sp := & ShortestPaths { } sp . initializeSingleSource ( g , s ) h := queryHeap { priorityQueue { } , map [ graph . NodeID ] * pqItem { } } g . IterateAllNodes ( func ( u graph . NodeID ) { item := & pqItem { u , sp . nodesMap [ u ] . d , h . Len ( ) } h . priorityQueue = append ( h . priorityQueue , item ) h . m [ u ] = item } ) heap . Init ( & h . priorityQueue ) for h . Len ( ) > 0 { u := sp . extractMin ( & h ) g . IterateAdjacencyNodes ( u , func ( v graph . NodeID ) { w , _ := g . Weight ( u , v ) newWeight := sp . relax ( u , v , w ) if newWeight > 0 { if vItem , ok := h . m [ v ] ; ok { vItem . priority = newWeight heap . Fix ( & h . priorityQueue , vItem . index ) } } } ) } return sp }
Dijkstra implements the dijkstra shortest path algorithm
Dijkstra implements the dijkstra shortest path algorithm
// update key