Is this really true? Using a pure Dijkstra would make the agents run the path with the least nodes not the shortest one.
How do you get that idea? As far as I know Dijkstra works on weighted graphs (weight = distance e.g.) and selects the path from one node to every other node that is the least weighted one (in this case the shortest).