Алгоритм Дейкстры является одним из самых быстрых для поиска кратчайших расстояний он некоторой вершины до всех остальных. При работе алгоритма используются следующие структуры данных: KR[i] - текущее кратчайшее растояние от начальной до i-й вершины. A[i,j] - длина ребра от i-й до j-й вершины. start - начальная вершина. Собственно сам алгоритм:

0. для всех i, KR[i]=Бесконечность
1. Curr=Start
2. Пометить Curr
3. для всех i, если KR[curr]>KR[i]+A[i,curr], то KR[curr]=KR[i]+A[i,curr]
4. Если все вершины помечены, то алгоритм завершен.
5. curr=непомеченная вершина с минимальным KR
6. Перейти к 2

Сложность алгоритма - O(N^2)