<commit_before>package pathfinding

func Dijkstra() {
	panic("Not yet implemented")
}<commit_msg>Pretty lame implementation (from wikipedia) to get started.<commit_after>package pathfinding

func minDist(dist map[*Node] int) *Node {
	var result_node *Node
	min := int(^uint(0) >> 1)
	for node, _dist := range dist {
		if min >= _dist {
			result_node = node
			min = _dist
		}
	}
	return result_node
}

func removeFromQ(Q []*Node, n *Node) []*Node {
	var result []*Node
	for _, node := range Q {
		if node != n {
			result = append(result, node)
		}
	}
	return result
}

func dist_between(n1 *Node, n2 *Node) int {
	return 0
}

func Dijkstra(graph *Graph) []*Node {
	MAX_INT := int(^uint(0) >> 1)
	var path []*Node
	var Q []*Node
	dist := make(map[*Node] int, len(graph.nodes))

	for _, node := range graph.nodes {
		dist[node] = MAX_INT
	}
	dist[graph.start] = 0
	copy(graph.nodes, Q)
	for len(Q) != 0 {
		u := minDist(dist)
		if dist[u] == MAX_INT {
			break
		}
		Q = removeFromQ(Q, u)
		for _, v := range graph.adjacentNodes(u) {
			alt := dist[u] + dist_between(u, v)
			if alt < dist[u] {
				dist[v] = alt
				v.parent = u
				//Reorder v in Q
			}
		}
	}
	return path
}
{'fraction_non_alphanumeric': 0.15293118096856415, 'fraction_numerical': 0.0076465590484282074, 'mean_word_length': 3.252707581227437, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6144621', 'n_tokens_mistral': 509, 'n_tokens_neox': 460, 'n_words': 130}