Buenas, me sumo a la discusión.
A mi también me dieron resultados similares, un poco más costosa la implementación con heap (pero una diferencia despreciable en la cantidad total de ciclo que lleva el dijkstra) cuando uso el grafo de 1000 nodos. Creo que va por ese lado: el recorrer, para cada nodo, todos sus vecinos y verificar si se puede llegar a estos de forma más "rápida" termina siendo muy costoso y oculta la diferencia en el costo de encontrar el nodo con distancia mínima en cada paso.
Lo que mencionas sobre llegar a cualquier nodo en pocos pasos, también me dió algo así, lo que pude observar es que el grafo en k1000.mat es muy denso, si te fijas no hay ninguna distancia en la matriz de adyacencia que tenga el valor de inf definido en la wiki (la cantidad de nodos me dio 1e3 y la cantidad de aristas 1e6). Entiendo que esto quiere decir que cada nodo esta conectado con todo el resto aunque sea con una distancia grande. Tal vez si no estuviesen todos los nodos conectados y no tuvieses que, en cada caso, revisar si es necesario actualizar la distancia asignada a cada nodo (porque no todos los nodos serian alcanzables desde el nodo que estas analizando) la diferencia de costo de ejecución entre las implementaciones sería más notorio.
Así lo pense yo, pero puedo estarle errando en algún concepto.
Saludos!