The Dijkstra's algorithm was initially designed to solve the single-source shortest path problem for a graph. Thus, the algorithm finds the lowest-cost route to everywhere from a single point. We will learn how to make use of it with two different approaches.
The first thing to do is import the binary heap class from the Game Programming Wiki (GPWiki) into our project, given that neither the .Net framework nor Mono has a defined structure for handling binary heaps or priority queues.
For downloading the source file and more information regarding GP Wiki's binary heap, please refer to the documentation online available at http://content.gpwiki.org/index.php/C_sharp:BinaryHeapOfT.
We will learn how to implement the Dijkstra algorithm using the same number of parameters as the other algorithms, and then explain how to modify it to make maximum use of it according to its original purpose.
GetPathDijkstra
function with its internal variables:public List<Vertex> GetPathDijkstra(GameObject srcObj, GameObject dstObj) { if (srcObj == null || dstObj == null) return new List<Vertex>(); Vertex src = GetNearestVertex(srcObj.transform.position); Vertex dst = GetNearestVertex(dstObj.transform.position); GPWiki.BinaryHeap<Edge> frontier = new GPWiki.BinaryHeap<Edge>(); Edge[] edges; Edge node, child; int size = vertices.Count; float[] distValue = new float[size]; int[] previous = new int[size]; // next steps }
node = new Edge(src, 0); frontier.Add(node); distValue[src.id] = 0; previous[src.id] = src.id; for (int i = 0; i < size; i++) { if (i == src.id) continue; distValue[i] = Mathf.Infinity; previous[i] = -1; }
while (frontier.Count != 0) { node = frontier.Remove(); int nodeId = node.vertex.id; // next steps } return new List<Vertex>();
if (ReferenceEquals(node.vertex, dst)) { return BuildPath(src.id, node.vertex.id, ref previous); }
edges = GetEdges(node.vertex); foreach (Edge e in edges) { int eId = e.vertex.id; if (previous[eId] != -1) continue; float cost = distValue[nodeId] + e.cost; if (cost < distValue[e.vertex.id]) { distValue[eId] = cost; previous[eId] = nodeId; frontier.Remove(e); child = new Edge(e.vertex, cost); frontier.Add(child); } }
The Dijkstra algorithm works in a similar way to BFS, but considers non-negative edge costs in order to build the best route from the source vertex to every other one. That's why we have an array for storing the previous vertex.
We will learn how to modify the current Dijkstra algorithm in order to approach the problem using pre-processing techniques and optimizing the path-finding time. It can be seen as three big steps: modifying the main algorithm, creating the pre-processing function (handy in editor mode, for example), and, finally, defining the path-retrieval function.
public int[] Dijkstra(GameObject srcObj)
return previous;
Vertex dst = GetNearestVertex(dstObj.transform.position);
Graph
class:List<int[]> routes = new List<int[]>();
DijkstraProcessing
:public void DijkstraProcessing() { int size = GetSize(); for (int i = 0; i < size; i++) { GameObject go = vertices[i].gameObject; routes.add(Dijkstra(go)); } }
GetPathDijkstra
function for path retrieval:public List<Vertex> GetPathDijkstra(GameObject srcObj, GameObject dstObj) { List<Vertex> path = new List<Vertex>(); Vertex src = GetNearestVertex(srcObj); Vertex dst = GetNearestVertex(dstObj); return BuildPath(src.id, dst.id, ref routes[dst.id]); }
In case you haven't noticed, we didn't implement the method BuildPath
. This is because we talked about it at the end of the Depth-First Search recipe.