Maybe you can use A* algorithm as a better alternative to dijkstra and use a metric function as a common heuristic to group or flag your vertices in a an appropriate way. 

Best regards.