Двухточечный путь на графике

Я хочу, чтобы алгоритм мог находить оптимальный путь между двумя вершинами графа (с положительными значениями int). Дело в том, что мой граф относительно большой (до 100 вершин). Я рассмотрел алгоритм Дейкстры, но при поиске в сети большинство реализаций используют матрицу смежности, которая в моем случае будет 100×100.

Если бы вы могли порекомендовать мне определенный источник для чтения и изучения, или даже лучше предоставить мне реализацию на С ++, это будет здорово.

PS: алгоритм должен выводить требуемый маршрут, а не только кратчайшее расстояние между двумя точками.

Спасибо за ваше время.