Dijkstra - przyśpieszenie algorytmu

Jak można przyśpieszyć działanie algorytmu Dijkstry?
Do przechowywania danych mam kilka tablic:
Sąsiedzi są tablicą dwuwymiarową, gdzie sasiedzi[x][y] są sąsiednimi wierzchołkami z sasiedzi[x][0].
koszty[x] - koszt dojścia do x-tego wierzchołka
poprzednicy[x] - indeks poprzedniego wierzchołka dla x-tego wierzchołka
kopiec[x] - kolejka, gdzie x-te pole w kopcu zawiera numer wierzchołka, który się w nim znajduje (kopiec binarny)
polozenie[x] - indeks, jaki zajmuje w kopcu x-ty wierzchołek
dane - informacje podane przez użytkownika
czyStos[x] - jeśli dla x-tego wierzchołka znaleziono najkrótszą trasę, to ustawiam na true

Czy opisanie grafu z użyciem normalnej listy + jednowymiarowej tablicy wskaźników może istotnie przyspieszyć działanie algorytmu? Największa ilość danych na której muszę operować to 2000 * 2000.

1.
czy mógłbyś określić otrzymywane czasy i Twój algorytm ?
przy użyciu tych samych elementów można zbudować algorytmy o istotnie różnych czasach
wykonania 
np. sortowanie bąbelkowe, quicksort, itp. inne algorytmy sortowania 


2.
np. na
http://rafalnowak.pl/wiki​/index.php​?title=Algorytm_Dijkstry
jest realizacja tego algorytmu przy pomocy kopca
autor chwali się że jest szybki.
 

inny na
http://www.algorytm.org​/algorytmy-grafowe​/algorytm-dijkstry​/dijkstra-kopce-c.html

porównaj te czasy ze swoim algorytmem.

Mój kod oparłam na tym algorytmie, na wersji z kopcem:
http://edu.i-lo.tarnow.pl/inf/alg/001_search/0138.php

Moje czasy przy małej ilości danych to 0,001 / 0,002, przy około 1000 rekordów 0,639, a przy +1000000 nawet nie chce mi się czekać aż policzy wynik.
Mój graf zawsze wygląda analogicznie:

o---o---o---o
|   |   |   |
o---o---o---o
|   |   |   |
o---o---o---o
|   |   |   |
o---o---o---o
Użytkownik wczytuje same wierzchołki i na ich podstawie wyznaczam sąsiadów każdego wierzchołka oraz obliczam wagi.
No i sama implementuję struktury, nie korzystam z gotowych kontenerów.

nie za bardzo zrozumiałem który algorytm użyłeś
zastanów się jaka jest złożoność użytego przez Ciebie algorytmu

na zacytowanej przez Ciebie stronie można wyczytać
"
Podstawowym zyskiem zastosowania kolejki priorytetowej w algorytmie Dijkstry jest zmniejszenie klasy złożoności obliczeniowej z O(n2) na O(n log n).
"

dlatego może obserwowany przez Ciebie efekt nie jest taki dziwny