If the player, as in human player is exploring the map, what do you need dijkstra for? I'll assume you mean to get AI to explore the map? dijkstra would be fine for that.

Take a look at the A* (pronounced A-star) algorithm. That's used for pathfinding.

If your searching the map for a certain type of object, and you don't know where the closest object of that type is on the map - use Dijkstra and terminate it when an object of the correct type is found.

A possibility is to set individual units to "explore" tasks. Then, the unit would examine adjacent tiles and determine which movement would reveal the highest amount of terrain (that is, it would move directly into uncharted territory). If no adjacent tile would reveal terrain, I would suggest finding the nearest unrevealed tile and moving straight to that tile. An additional constraint that would be useful is to only consider accessible unrevealed tiles only (both when examining adjacent tile revealing power and new destinations), so units don't spend time exploring areas that cannot be reached yet, and neither do they try to get to them.

Now, if you have several units exploring at the same time, you don't want them to overlap each other. This would happen naturally if the units are close to each other (the first's exploration would cause the second one to take a new direction), but units in their "move towards new exploration start point" would probably annoy each other (since the closest unexplored point might become explored during transit). I would cause an exploring unit's movement to be interrupted if another unit explores its destination tile, thus prompting the stopped unit to compute a new path, possibly to a new area.