The prototypical graph search algorithm Dijkstra's algorithm for finding the shortest paths between nodes in a graph which works for unbounded non-negative weights has a time complexity for $$O(|V|^2)$$ where $$|V|$$ is the number of nodes/vertices in a graph which is in $$P$$.
• And look into A* search to understand Dijkstra can be improved. Peter Norvig (of the book "AI a Modern Approach") has some interesting youtube videos on the subject. Sep 21 at 11:47