1. A method for testing a navigation graph service comprising: providing a directed graph based on the navigation graph service, wherein nodes of the directed graph are associated with load levels; determining, by one or more hardware processors, a set of paths (S) between a root node (R) in the directed graph and other non-root nodes in the directed graph based on the load levels associated with the nodes, wherein each path in the set of paths (S) corresponds to an edge-disjoint path between R and another non-root node in the directed graph; generating, by the one or more hardware processors, a testing script for an arbitrary performance testing tool based on the set of paths (S); and executing the testing script using the performance testing tool.