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.
- Define the
GetPathDijkstrafunction 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 } - Add the source node to the heap (working as a priority queue) and assign a distance value of infinity to all of them but the source node:
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; } - Define a loop to iterate while the queue is not empty:
while (frontier.Count != 0) { node = frontier.Remove(); int nodeId = node.vertex.id; // next steps } return new List<Vertex>(); - Code the procedure when arriving at the destination:
if (ReferenceEquals(node.vertex, dst)) { return BuildPath(src.id, node.vertex.id, ref previous); } - Otherwise, process the visited nodes and add its neighbors to the queue, and return the path (not empty if there is a path from source to destination vertex):
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.
- Modify the main function's signature:
public int[] Dijkstra(GameObject srcObj)
- Change the returning value:
return previous;
- Remove the lines from step 4 in the How to do it section:
- Also, delete the following line at the beginning:
Vertex dst = GetNearestVertex(dstObj.transform.position);
- Create a new member value to the
Graphclass:List<int[]> routes = new List<int[]>();
- Define the pre-processing function, called
DijkstraProcessing:public void DijkstraProcessing() { int size = GetSize(); for (int i = 0; i < size; i++) { GameObject go = vertices[i].gameObject; routes.add(Dijkstra(go)); } } - Implement a new
GetPathDijkstrafunction 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.