There's more...

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:

1. Modify the main function's signature:

public int[] Dijkstra(GameObject srcObj) 

2. Change the returning value:

return previous; 

3. Remove the lines from step 4 of the How to do it section:

if (ReferenceEquals(node.vertex, dst)) 
{ 
    return BuildPath(src.id, node.vertex.id, ref previous); 
}

Also, delete the following line at the beginning:

Vertex dst = GetNearestVertex(dstObj.transform.position);

4. Create a new member value for the Graph class:

List<int[]> routes = new List<int[]>(); 

5. 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)); 
    } 
} 

6. Implement a new 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 BuildPath method. This is because we talked about it at the end of Chapter 2, Navigation, in the recipe Finding your way out of a maze with DFS.