glacial peak
As the title says I am working on implementing dijkstra's algorithm for pathfinding on a grid.
this is my current implementation:
class_name DijkstraGrid
class PriorityQueue:
var q: Array
func _init():
q = []
func sort_func(a, b):
return a.priority - b.priority
func enqueue(element, priority):
q.append({ el=element, priority=priority})
q.sort_custom(func(a,b): sort_func(a, b))
func dequeue():
return q.pop_front().el
func is_empty():
return len(q) == 0
var vec_nums: int
var adj: Array
func _init(v: int):
vec_nums = v
adj = []
adj.resize(v)
adj.fill([])
func add_edge(u, v, w):
adj[u].append({v = v, w = w})
adj[v].append({v = u, w = w})
func shortest_path(src):
var pq = PriorityQueue.new()
var dist = []
dist.resize(vec_nums)
dist.fill((INF))
var visited = []
visited.resize(vec_nums)
visited.fill(false)
pq.enqueue(src, 0)
dist[src] = 0
while not pq.is_empty():
var u: int = pq.dequeue()
if visited[u]:
continue
visited[u] = true
for adjj in adj[u]:
var v = adjj.v # vector
var w = adjj.w # weight
if not visited[v] and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
pq.enqueue(v, dist[v])
print("Vertex Distance from Source")
for i in range(vec_nums):
var fmt = "vec: %s\tdistance from %s -> %s" % [i, src, "Infinity" if dist[i] == INF else str(dist[i])]
print(fmt)
I am expecting to run the following code:
var v = 7
var g = DijkstraGrid.new(v)
g.add_edge(0, 1, 2)
g.add_edge(0, 2, 6)
g.add_edge(1, 3, 5)
g.add_edge(2, 3, 8)
g.add_edge(3, 4, 10)
g.add_edge(3, 5, 15)
g.add_edge(4, 6, 2)
g.add_edge(5, 6, 6)
g.shortest_path(0)
and get correct distances as the image but i do not
