The navigator subclass, such as the NavigatorNavmesh, is indeed tied to the navigation mesh. It's an implementation of my interface where it is tied closely to how the navigation mesh stores data. The Navigator is my path finder and my path smoother. This object serves several purposes for me. It represents the state of navigation for a particular entity. The navigators could be updated from multiple threads, modifying their internal search state and referencing the navigation mesh in a read only manner, they could be updated serially in a time spliced sort of manner(allowing many paths to be in progress simultaneously), and it shields the rest of the code from the choice of navigation system I'm using, allowing me to change it easier at a later point. Also, since it maintains its own internal state which may involve functionality closely related to the navigation system, it can handle the dynamic aspects of path following was well, such as string pulling, often implemented in a way that requires regular maintenance of the path which can be encapsulated in the navigator.
You don't have to do it this way. You can just create a function on your map class or something if you want to start simple that solves a path and gives you back an immediate result in the form of filling in a result object or a list of path nodes, etc.
Status TileMap::FindPath( PathResult & resultOut, const vec2 & src, const vec2 & dst, ... );
Path nodes hold the state of the navigation query at a particular state, the code, the parent pointer for reconstructing the path when the goal is found, etc. This is temporary scratch data and doesn't belong in the same objects as your Tiles, which presumably hold a reference to the image used for that tile, whether the tile is solid or not. I think about the tile map in a 2d game as an image, and the tiles as the pixels of the image, the color channels as the data about those tiles. I would not bloat that data with pathfinding search state. Other than bloat, if the tile map, of which there is presumably only 1 copy of, contains the search state, you can only solve for 1 query at a time.
I would suggest, even if you keep it as a simple function call for an immediate path solution and nothing fancy like a navigator, that you keep the search state separate from the tiles.
something like
struct PathNode
{
int x,y; // coordinate of node in tile map
// search state
PathNode * mParent;
float g, f;
....
}