We are given an \(80\times80\) matrix \(M\). A path starts at the upper-left cell \((0,0)\), ends at the lower-right cell \((79,79)\), and may move one step up, down, left, or right as long as it stays inside the matrix. The cost of a path is the sum of all visited cell values, so both the starting cell and the ending cell contribute to the total.
The extra freedom to move in all four directions is the essential difference from the earlier path-sum problems. Once left and up moves are allowed, the dependency graph of the cells has cycles, so there is no row-by-row or column-by-column order that makes a one-pass dynamic program valid.
Let \(d(r,c)\) denote the minimum possible path sum for any valid path from \((0,0)\) to \((r,c)\). The implementations solve for this quantity by turning the matrix into a weighted graph and then running Dijkstra's algorithm.
Each cell is a vertex. Two vertices are connected when the corresponding cells are orthogonal neighbors in the grid. If a step moves from \((r,c)\) to a neighbor \((r',c')\), the step cost is the value of the destination cell \(M_{r',c'}\). With this convention, a path
$$P=((r_0,c_0),(r_1,c_1),\dots,(r_k,c_k))$$
has total cost
$$\operatorname{cost}(P)=M_{r_0,c_0}+\sum_{t=1}^{k} M_{r_t,c_t}=\sum_{t=0}^{k} M_{r_t,c_t}.$$
So the Project Euler question is exactly a shortest-path problem from the start vertex to the target vertex.
All matrix entries are positive, so every directed edge has positive weight. That matters twice. First, any path containing a cycle can be shortened by deleting the cycle, so an optimal path never needs to revisit a cell. Second, positive weights are exactly the hypothesis that makes Dijkstra's greedy extraction rule correct.
The minimum cost function satisfies the relation
$$d(0,0)=M_{0,0},$$
and for every other cell,
$$d(r,c)=M_{r,c}+\min_{(u,v)\in \mathcal{N}(r,c)} d(u,v),$$
where \(\mathcal{N}(r,c)\) is the set of in-bounds orthogonal neighbors of \((r,c)\).
This is the right optimal-substructure statement: the last step into \((r,c)\) must come from one of its neighbors. The difficulty is that these equations are coupled. A value such as \(d(r,c)\) may depend on \(d(r,c+1)\), while \(d(r,c+1)\) may also depend on \(d(r,c)\) through a different route. That feedback loop is exactly why Problems 81 and 82 admit simpler dynamic programs but Problem 83 does not.
Dijkstra's algorithm keeps a tentative distance for each cell and a min-priority queue of candidate states. Whenever the cell with the smallest tentative value is extracted, that value is final. The relaxation step for a neighbor \((r',c')\) is
$$\text{candidate}=d(r,c)+M_{r',c'},$$
and we update the neighbor if this candidate is smaller than its current best known value.
The correctness proof is the standard positive-weight argument. Assume that some extracted cell is the first one whose tentative value is larger than the true optimum. Along a truly optimal path to that cell, look at the first cell not yet extracted, and let the previous cell on that path be its predecessor. The predecessor must have been extracted earlier with its correct value, so relaxing the next edge would have inserted a tentative value no larger than the true optimum of the final cell. That contradicts the choice of the supposedly first bad extraction. Therefore every extracted cell is finalized correctly, including the destination.
The sample used by the implementation is
$$\begin{pmatrix} 131 & 673 & 234 & 103 & 18 \\ 201 & 96 & 342 & 965 & 150 \\ 630 & 803 & 746 & 422 & 111 \\ 537 & 699 & 497 & 121 & 956 \\ 805 & 732 & 524 & 37 & 331 \end{pmatrix}.$$
One optimal route is
$$(0,0)\to(1,0)\to(1,1)\to(1,2)\to(0,2)\to(0,3)\to(0,4)\to(1,4)\to(2,4)\to(2,3)\to(3,3)\to(4,3)\to(4,4).$$
Its cost is
$$131+201+96+342+234+103+18+150+111+422+121+37+331=2297.$$
The upward move from \((1,2)\) back to \((0,2)\) is the key feature: the best path is not monotone. That single step already shows why a right-and-down dynamic program is no longer enough.
The C++, Python, and Java implementations all read the matrix, build a two-dimensional distance table, and initialize every entry to infinity except the start cell. The priority queue is seeded with the start state whose cost is the value of the upper-left cell itself.
They then repeat the same loop: extract the state with minimum tentative cost, ignore it if the queue entry is stale, and otherwise try all four orthogonal neighbors. Whenever moving into a neighbor produces a smaller total, the implementation records the better distance and pushes a fresh queue entry. This is the lazy-heap version of Dijkstra: there is no explicit decrease-key operation, so obsolete entries are simply skipped when they reappear.
The three languages differ only in presentation details. The C++ implementation also checks the standard 5x5 sample and can stop as soon as the target cell is extracted, while the Python and Java implementations continue the same relaxation process until the queue is empty. In every case, the reported answer is the finalized distance of the bottom-right cell.
If the matrix has \(R\) rows and \(C\) columns, then the graph has \(V=RC\) vertices and at most \(E\le 4RC\) directed neighbor relaxations. With a binary heap, Dijkstra runs in
$$O(E\log V)=O(RC\log(RC)).$$
For an \(n\times n\) grid this is \(O(n^2\log n)\), since \(\log(n^2)=2\log n\).
The distance table uses \(O(RC)\) space, and the priority queue also stays within \(O(RC)\) stored states up to constant-factor duplicates from the lazy updates. For the actual \(80\times80\) instance, this means only \(6400\) vertices and at most \(25600\) neighbor edges, which is easily small enough for an ordinary heap-based shortest-path computation.
Gegeben ist eine \(80\times80\)-Matrix \(M\). Ein Pfad beginnt in der linken oberen Ecke \((0,0)\), endet in der rechten unteren Ecke \((79,79)\) und darf sich jeweils einen Schritt nach oben, unten, links oder rechts bewegen, solange er innerhalb der Matrix bleibt. Die Kosten eines Pfades sind die Summe aller besuchten Zellenwerte; sowohl das Startfeld als auch das Zielfeld zählen also mit.
Die zusätzliche Freiheit, in alle vier Richtungen gehen zu dürfen, ist der entscheidende Unterschied zu den früheren Path-Sum-Aufgaben. Sobald auch Bewegungen nach links und oben erlaubt sind, enthält der Abhängigkeitsgraph der Zellen Zyklen. Deshalb gibt es keine feste Zeilen- oder Spaltenreihenfolge, in der ein einmaliger dynamischer Programmierdurchlauf korrekt wäre.
Sei \(d(r,c)\) die kleinste mögliche Pfadsumme unter allen gültigen Pfaden von \((0,0)\) nach \((r,c)\). Die Implementierungen berechnen genau diese Größe, indem sie die Matrix als gewichteten Graphen auffassen und darauf Dijkstras Algorithmus anwenden.
Jede Zelle wird als Knoten interpretiert. Zwei Knoten sind genau dann verbunden, wenn die zugehörigen Zellen orthogonale Nachbarn im Gitter sind. Führt ein Schritt von \((r,c)\) zu einem Nachbarn \((r',c')\), dann sind die Schrittkosten gleich dem Wert der Zielzelle \(M_{r',c'}\). Mit dieser Konvention hat ein Pfad
$$P=((r_0,c_0),(r_1,c_1),\dots,(r_k,c_k))$$
die Gesamtkosten
$$\operatorname{cost}(P)=M_{r_0,c_0}+\sum_{t=1}^{k} M_{r_t,c_t}=\sum_{t=0}^{k} M_{r_t,c_t}.$$
Die Euler-Aufgabe ist damit exakt ein Kürzeste-Wege-Problem vom Startknoten zum Zielknoten.
Alle Matrixeinträge sind positiv, also haben auch alle gerichteten Kanten positive Gewichte. Das ist in zweierlei Hinsicht wichtig. Erstens kann jeder Pfad mit einem Zyklus durch Entfernen dieses Zyklus nur billiger werden, also muss ein optimaler Pfad keine Zelle erneut besuchen. Zweitens ist genau diese Positivität die Voraussetzung dafür, dass Dijkstras gierige Extraktionsregel korrekt ist.
Die minimale Kostenfunktion erfüllt
$$d(0,0)=M_{0,0},$$
und für jede andere Zelle
$$d(r,c)=M_{r,c}+\min_{(u,v)\in \mathcal{N}(r,c)} d(u,v),$$
wobei \(\mathcal{N}(r,c)\) die Menge der orthogonalen Nachbarn von \((r,c)\) innerhalb der Matrix bezeichnet.
Das ist die richtige Optimalitätsaussage: Der letzte Schritt nach \((r,c)\) muss aus einer Nachbarzelle kommen. Die Schwierigkeit ist, dass diese Gleichungen gekoppelt sind. Ein Wert wie \(d(r,c)\) kann von \(d(r,c+1)\) abhängen, während \(d(r,c+1)\) über einen anderen Weg wiederum von \(d(r,c)\) abhängen kann. Genau diese Rückkopplung erklärt, warum die Aufgaben 81 und 82 einfachere dynamische Programme zulassen, Problem 83 aber nicht.
Dijkstras Algorithmus speichert für jede Zelle einen vorläufigen Abstand und hält zusätzlich eine Min-Prioritätswarteschlange mit Kandidatenzuständen. Immer wenn die Zelle mit dem kleinsten vorläufigen Wert entnommen wird, ist dieser Wert bereits endgültig. Der Relaxationsschritt für einen Nachbarn \((r',c')\) lautet
$$\text{candidate}=d(r,c)+M_{r',c'},$$
und der Nachbar wird aktualisiert, falls dieser Kandidat kleiner ist als sein bisher bester bekannter Wert.
Der Korrektheitsbeweis ist das übliche Argument für positive Gewichte. Angenommen, es gäbe eine entnommene Zelle, deren vorläufiger Wert als erste größer als das wahre Optimum ist. Betrachte auf einem tatsächlich optimalen Pfad zu dieser Zelle die erste noch nicht entnommene Zelle und ihren Vorgänger auf demselben Pfad. Der Vorgänger muss zuvor mit seinem korrekten Wert entnommen worden sein; beim Relaxieren der nächsten Kante wäre daher ein vorläufiger Wert eingetragen worden, der nicht größer als das wahre Optimum der Endzelle ist. Das widerspricht der Annahme, dass gerade die angeblich erste falsche Entnahme erfolgt ist. Also wird jede entnommene Zelle korrekt finalisiert, insbesondere das Ziel.
Das von der Implementierung verwendete Beispiel ist
$$\begin{pmatrix} 131 & 673 & 234 & 103 & 18 \\ 201 & 96 & 342 & 965 & 150 \\ 630 & 803 & 746 & 422 & 111 \\ 537 & 699 & 497 & 121 & 956 \\ 805 & 732 & 524 & 37 & 331 \end{pmatrix}.$$
Ein optimaler Weg ist
$$(0,0)\to(1,0)\to(1,1)\to(1,2)\to(0,2)\to(0,3)\to(0,4)\to(1,4)\to(2,4)\to(2,3)\to(3,3)\to(4,3)\to(4,4).$$
Seine Kosten betragen
$$131+201+96+342+234+103+18+150+111+422+121+37+331=2297.$$
Der Schritt nach oben von \((1,2)\) zurück nach \((0,2)\) ist hier das entscheidende Detail: Der beste Pfad ist nicht monoton. Schon dieser einzelne Schritt zeigt, warum ein reines Rechts-unten-DP nicht mehr ausreicht.
Die Implementierungen in C++, Python und Java lesen alle dieselbe Matrix ein, legen eine zweidimensionale Abstandstabelle an und initialisieren sie überall mit Unendlich, außer im Startfeld. Die Prioritätswarteschlange wird mit dem Startzustand gefüllt, dessen Kosten dem Wert der linken oberen Zelle entsprechen.
Danach wiederholen sie dieselbe Schleife: den Zustand mit den kleinsten vorläufigen Kosten entnehmen, ihn überspringen, falls der Warteschlangeneintrag veraltet ist, und sonst alle vier orthogonalen Nachbarn prüfen. Wenn der Schritt in einen Nachbarn eine kleinere Gesamtsumme liefert, wird der bessere Abstand gespeichert und ein neuer Warteschlangeneintrag eingefügt. Das ist die faule Heap-Variante von Dijkstra: Eine explizite Decrease-Key-Operation gibt es nicht; veraltete Einträge werden einfach später verworfen.
Die drei Sprachen unterscheiden sich nur in Darstellungsdetails. Die C++-Implementierung prüft zusätzlich das Standardbeispiel \(5\times5\) und kann sofort abbrechen, sobald die Zielzelle entnommen wurde; die Python- und Java-Implementierungen führen denselben Relaxationsprozess bis zum Leerlaufen der Warteschlange fort. In allen Fällen ist die ausgegebene Antwort der finalisierte Abstand der rechten unteren Zelle.
Hat die Matrix \(R\) Zeilen und \(C\) Spalten, dann besitzt der Graph \(V=RC\) Knoten und höchstens \(E\le 4RC\) gerichtete Nachbarrelaxationen. Mit einem binären Heap läuft Dijkstra in
$$O(E\log V)=O(RC\log(RC)).$$
Für ein \(n\times n\)-Gitter ist das \(O(n^2\log n)\), denn \(\log(n^2)=2\log n\).
Die Abstandstabelle benötigt \(O(RC)\) Speicher, und auch die Prioritätswarteschlange bleibt bis auf konstante Faktoren durch die faulen Aktualisierungen in \(O(RC)\). Für die konkrete \(80\times80\)-Instanz bedeutet das nur \(6400\) Knoten und höchstens \(25600\) Nachbarschaftskanten; das ist für eine gewöhnliche Heap-basierte Kürzeste-Wege-Berechnung problemlos klein.
Bize \(80\times80\) boyutunda bir \(M\) matrisi verilir. Bir yol sol üst hücre \((0,0)\) noktasında başlar, sağ alt hücre \((79,79)\) noktasında biter ve matris dışına çıkmamak şartıyla her adımda yukarı, aşağı, sola veya sağa gidebilir. Bir yolun maliyeti ziyaret edilen bütün hücre değerlerinin toplamıdır; dolayısıyla hem başlangıç hücresi hem de bitiş hücresi toplama dahildir.
Dört yöne birden izin verilmesi, bu problemi önceki path-sum sorularından ayıran temel özelliktir. Sola ve yukarı hareket serbest bırakıldığında hücreler arasındaki bağımlılık grafiği döngüler içerir. Bu yüzden satır satır ya da sütun sütun ilerleyen tek geçişli bir dinamik program artık geçerli değildir.
\(d(r,c)\) ile \((0,0)\) noktasından \((r,c)\) noktasına giden bütün geçerli yollar arasındaki en küçük yol toplamını gösterelim. Uygulamalar tam olarak bu niceliği, matrisi ağırlıklı bir grafik olarak yorumlayıp Dijkstra algoritmasını çalıştırarak hesaplar.
Her hücre bir düğüm olarak düşünülür. İki düğüm, karşılık gelen hücreler ızgarada ortogonal komşuysa bağlıdır. Bir adım \((r,c)\) konumundan komşu \((r',c')\) konumuna gidiyorsa, adım maliyeti hedef hücrenin değeri olan \(M_{r',c'}\) olur. Bu sözleşmeyle
$$P=((r_0,c_0),(r_1,c_1),\dots,(r_k,c_k))$$
şeklindeki bir yolun toplam maliyeti
$$\operatorname{cost}(P)=M_{r_0,c_0}+\sum_{t=1}^{k} M_{r_t,c_t}=\sum_{t=0}^{k} M_{r_t,c_t}.$$
Dolayısıyla Euler sorusu tam olarak başlangıç düğümünden hedef düğüme giden bir en kısa yol problemidir.
Matristeki bütün girişler pozitiftir; bu da bütün yönlü kenar ağırlıklarının pozitif olduğu anlamına gelir. Bunun iki sonucu vardır. Birincisi, döngü içeren bir yol döngü çıkarılarak mutlaka ucuzlatılabilir; yani optimal bir yolun aynı hücreyi tekrar ziyaret etmesine gerek yoktur. İkincisi, Dijkstra'nın açgözlü olarak en küçük geçici değeri seçme kuralı tam da bu pozitiflik altında doğrudur.
En küçük maliyet fonksiyonu şu bağıntıyı sağlar:
$$d(0,0)=M_{0,0},$$
ve diğer her hücre için
$$d(r,c)=M_{r,c}+\min_{(u,v)\in \mathcal{N}(r,c)} d(u,v),$$
burada \(\mathcal{N}(r,c)\), \((r,c)\) hücresinin matris içinde kalan ortogonal komşular kümesidir.
Bu, doğru optimal alt yapı ifadesidir: \((r,c)\) hücresine yapılan son adım mutlaka bir komşudan gelmelidir. Fakat denklemler birbirine bağlıdır. Örneğin \(d(r,c)\), \(d(r,c+1)\) değerine bağlı olabilir; aynı anda \(d(r,c+1)\) de farklı bir rota üzerinden yeniden \(d(r,c)\) değerine bağlı olabilir. Problem 81 ve 82'deki daha basit dinamik programların burada çalışmamasının nedeni tam olarak bu geri besleme döngüsüdür.
Dijkstra algoritması her hücre için geçici bir uzaklık tutar ve aday durumları bir minimum öncelik kuyruğunda saklar. En küçük geçici değere sahip hücre kuyruktan çıkarıldığında, o değer artık kesindir. Bir komşu \((r',c')\) için gevşetme adımı
$$\text{candidate}=d(r,c)+M_{r',c'}$$
şeklindedir; eğer bu aday, komşu için bilinen en iyi değerden küçükse komşu güncellenir.
Doğruluk ispatı, pozitif ağırlıklar için kullanılan klasik argümandır. Diyelim ki kuyruktan çıkarılan bir hücre, gerçek optimumundan büyük bir geçici değerle çıkan ilk hücre olsun. Bu hücreye giden gerçekten optimal bir yol üzerinde, henüz çıkarılmamış ilk hücreye ve o yol üzerindeki öncülüne bakalım. Öncül hücre daha önce doğru değeriyle çıkarılmış olmalıdır; dolayısıyla bir sonraki kenar gevşetildiğinde, son hücrenin gerçek optimumundan büyük olmayan bir geçici değer kuyruğa eklenmiş olurdu. Bu da sözde ilk hatalı çıkarım varsayımıyla çelişir. Sonuç olarak kuyruktan çıkan her hücre, hedef dahil, doğru biçimde kesinleşir.
Uygulamanın doğrulama için kullandığı örnek şudur:
$$\begin{pmatrix} 131 & 673 & 234 & 103 & 18 \\ 201 & 96 & 342 & 965 & 150 \\ 630 & 803 & 746 & 422 & 111 \\ 537 & 699 & 497 & 121 & 956 \\ 805 & 732 & 524 & 37 & 331 \end{pmatrix}.$$
Optimal yollardan biri
$$(0,0)\to(1,0)\to(1,1)\to(1,2)\to(0,2)\to(0,3)\to(0,4)\to(1,4)\to(2,4)\to(2,3)\to(3,3)\to(4,3)\to(4,4).$$
Bu yolun maliyeti
$$131+201+96+342+234+103+18+150+111+422+121+37+331=2297.$$
\((1,2)\) noktasından tekrar yukarı çıkıp \((0,2)\) hücresine dönmek burada belirleyici ayrıntıdır: en iyi yol monoton değildir. Tek başına bu adım bile, yalnızca sağa ve aşağıya dayalı bir DP'nin artık yeterli olmadığını gösterir.
C++, Python ve Java uygulamaları matris verisini okur, iki boyutlu bir uzaklık tablosu kurar ve başlangıç hücresi dışında bütün değerleri sonsuzla başlatır. Öncelik kuyruğu, maliyeti sol üst hücrenin değeri olan başlangıç durumu ile doldurulur.
Daha sonra aynı döngü tekrar edilir: geçici maliyeti en küçük olan durum kuyruktan alınır, kuyruk girdisi bayatsa atlanır, değilse dört ortogonal komşunun tamamı denenir. Bir komşuya geçmek daha küçük bir toplam üretiyorsa daha iyi uzaklık kaydedilir ve kuyruğa yeni bir kayıt eklenir. Bu, Dijkstra'nın tembel yığın sürümüdür: açık bir decrease-key işlemi yoktur; eskimiş kayıtlar daha sonra çıktıklarında yalnızca görmezden gelinir.
Üç dil arasındaki fark yalnızca sunum ayrıntılarındadır. C++ uygulaması standart \(5\times5\) örneği ayrıca doğrular ve hedef hücre kuyruktan çıktığı anda durabilir; Python ve Java uygulamaları ise aynı gevşetme sürecini kuyruk boşalana kadar sürdürür. Her durumda yazdırılan sonuç, sağ alt hücrenin kesinleşmiş uzaklığıdır.
Matrisin \(R\) satırı ve \(C\) sütunu varsa grafikte \(V=RC\) düğüm ve en fazla \(E\le 4RC\) yönlü komşuluk gevşetmesi vardır. İkili yığın kullanıldığında Dijkstra'nın çalışma süresi
$$O(E\log V)=O(RC\log(RC)).$$
\(n\times n\) bir ızgarada bu, \(\log(n^2)=2\log n\) olduğu için \(O(n^2\log n)\) biçimine gelir.
Uzaklık tablosu \(O(RC)\) alan kullanır; tembel güncellemelerden doğan sabit katsayılı tekrarlar hesaba katılsa bile öncelik kuyruğu da \(O(RC)\) içinde kalır. Gerçek \(80\times80\) örneğinde bu yalnızca \(6400\) düğüm ve en fazla \(25600\) komşu kenar demektir; dolayısıyla sıradan bir yığın tabanlı en kısa yol hesabı için oldukça küçüktür.
Se nos da una matriz \(80\times80\) \(M\). Un camino comienza en la celda superior izquierda \((0,0)\), termina en la celda inferior derecha \((79,79)\) y puede avanzar un paso hacia arriba, abajo, izquierda o derecha siempre que permanezca dentro de la matriz. El coste del camino es la suma de todos los valores visitados, de modo que tanto la celda inicial como la celda final cuentan en el total.
La posibilidad de moverse en las cuatro direcciones es la diferencia esencial frente a los problemas anteriores de sumas de caminos. En cuanto se permiten pasos hacia la izquierda y hacia arriba, el grafo de dependencias entre celdas contiene ciclos, y ya no existe un orden fijo por filas o columnas que permita un programa dinámico correcto en una sola pasada.
Sea \(d(r,c)\) la mínima suma posible entre todos los caminos válidos que van de \((0,0)\) a \((r,c)\). Las implementaciones calculan exactamente esta cantidad convirtiendo la matriz en un grafo ponderado y aplicando después el algoritmo de Dijkstra.
Cada celda se interpreta como un vértice. Dos vértices están conectados cuando las celdas correspondientes son vecinas ortogonales en la rejilla. Si un paso va de \((r,c)\) a un vecino \((r',c')\), el coste de ese paso es el valor de la celda de destino \(M_{r',c'}\). Con esta convención, un camino
$$P=((r_0,c_0),(r_1,c_1),\dots,(r_k,c_k))$$
tiene coste total
$$\operatorname{cost}(P)=M_{r_0,c_0}+\sum_{t=1}^{k} M_{r_t,c_t}=\sum_{t=0}^{k} M_{r_t,c_t}.$$
Por tanto, la pregunta de Project Euler es exactamente un problema de camino mínimo desde el vértice inicial hasta el vértice objetivo.
Todas las entradas de la matriz son positivas, así que todos los pesos de arista también lo son. Eso importa por dos razones. Primero, cualquier camino que contenga un ciclo puede abaratarse eliminando dicho ciclo, de modo que un camino óptimo no necesita revisitar una celda. Segundo, la positividad es precisamente la hipótesis bajo la cual la regla voraz de extracción de Dijkstra es correcta.
La función de coste mínimo satisface
$$d(0,0)=M_{0,0},$$
y para cualquier otra celda
$$d(r,c)=M_{r,c}+\min_{(u,v)\in \mathcal{N}(r,c)} d(u,v),$$
donde \(\mathcal{N}(r,c)\) es el conjunto de vecinos ortogonales de \((r,c)\) que permanecen dentro de la matriz.
Esta es la afirmación correcta de subestructura óptima: el último paso hacia \((r,c)\) debe venir de alguna celda vecina. La dificultad es que las ecuaciones están acopladas. Un valor como \(d(r,c)\) puede depender de \(d(r,c+1)\), mientras que \(d(r,c+1)\) también puede depender de \(d(r,c)\) a través de otra ruta. Ese bucle de realimentación explica exactamente por qué los Problemas 81 y 82 admiten programas dinámicos más simples, mientras que el Problema 83 no.
El algoritmo de Dijkstra mantiene una distancia tentativa para cada celda y una cola de prioridad mínima con estados candidatos. Siempre que se extrae la celda con el menor valor tentativo, ese valor ya es definitivo. El paso de relajación para un vecino \((r',c')\) es
$$\text{candidate}=d(r,c)+M_{r',c'},$$
y se actualiza el vecino si ese candidato mejora el mejor valor conocido hasta ese momento.
La demostración de corrección es el argumento estándar para pesos positivos. Supongamos que alguna celda extraída es la primera cuyo valor tentativo supera al óptimo real. En un camino realmente óptimo hacia esa celda, miramos la primera celda que todavía no haya sido extraída y su predecesora en el mismo camino. La predecesora tuvo que extraerse antes con su valor correcto; por tanto, al relajar la arista siguiente se habría insertado un valor tentativo no mayor que el óptimo real de la celda final. Eso contradice la elección de la supuesta primera extracción incorrecta. Luego toda celda extraída queda finalizada correctamente, incluida la meta.
La muestra utilizada por la implementación es
$$\begin{pmatrix} 131 & 673 & 234 & 103 & 18 \\ 201 & 96 & 342 & 965 & 150 \\ 630 & 803 & 746 & 422 & 111 \\ 537 & 699 & 497 & 121 & 956 \\ 805 & 732 & 524 & 37 & 331 \end{pmatrix}.$$
Un camino óptimo es
$$(0,0)\to(1,0)\to(1,1)\to(1,2)\to(0,2)\to(0,3)\to(0,4)\to(1,4)\to(2,4)\to(2,3)\to(3,3)\to(4,3)\to(4,4).$$
Su coste vale
$$131+201+96+342+234+103+18+150+111+422+121+37+331=2297.$$
El movimiento hacia arriba desde \((1,2)\) hasta \((0,2)\) es el detalle clave: el mejor camino no es monótono. Ese único paso ya muestra por qué un DP restringido a derecha y abajo deja de ser suficiente.
Las implementaciones en C++, Python y Java leen la matriz, construyen una tabla bidimensional de distancias e inicializan todo con infinito salvo la celda inicial. La cola de prioridad se arranca con el estado de partida, cuyo coste es precisamente el valor de la celda superior izquierda.
Después repiten el mismo ciclo: extraer el estado con menor coste tentativo, ignorarlo si la entrada de la cola ya quedó obsoleta y, en caso contrario, probar los cuatro vecinos ortogonales. Siempre que entrar en un vecino produce una suma más pequeña, la implementación guarda la nueva distancia y empuja una entrada fresca en la cola. Esta es la versión perezosa de Dijkstra con heap: no hay una operación explícita de decrease-key, así que las entradas antiguas simplemente se descartan cuando reaparecen.
Las tres versiones solo difieren en detalles de presentación. La implementación en C++ además verifica la muestra estándar \(5\times5\) y puede detenerse en cuanto se extrae la celda objetivo; las implementaciones en Python y Java continúan con el mismo proceso de relajación hasta vaciar la cola. En todos los casos, el valor informado es la distancia ya finalizada de la esquina inferior derecha.
Si la matriz tiene \(R\) filas y \(C\) columnas, entonces el grafo tiene \(V=RC\) vértices y a lo sumo \(E\le 4RC\) relajaciones dirigidas hacia vecinos. Con un heap binario, Dijkstra se ejecuta en
$$O(E\log V)=O(RC\log(RC)).$$
Para una rejilla \(n\times n\), esto se convierte en \(O(n^2\log n)\), ya que \(\log(n^2)=2\log n\).
La tabla de distancias usa \(O(RC)\) memoria, y la cola de prioridad también permanece en \(O(RC)\) salvo factores constantes debidos a las duplicaciones de la versión perezosa. En la instancia real \(80\times80\), eso significa solo \(6400\) vértices y como máximo \(25600\) aristas de vecindad, un tamaño muy cómodo para un cálculo estándar de caminos mínimos con heap.
题目给出一个 \(80\times80\) 的矩阵 \(M\)。路径从左上角单元 \((0,0)\) 出发，到右下角单元 \((79,79)\) 结束，并且每一步都可以向上、向下、向左或向右移动，只要不走出矩阵。路径代价是所有经过单元格数值的总和，因此起点和终点本身都要计入答案。
允许四个方向移动，是本题相对于前面路径和问题的根本变化。一旦允许向左和向上，单元之间的依赖关系就会形成环，不再存在一个按行或按列的固定顺序，可以让单次扫描的动态规划始终正确。
设 \(d(r,c)\) 表示从 \((0,0)\) 到 \((r,c)\) 的所有合法路径中，最小可能的路径和。C++、Python 和 Java 的实现计算的正是这个量；它们的做法是先把矩阵改写成带权图，再在图上运行 Dijkstra 算法。
把每个单元格看成一个顶点。若两个单元在网格中是正交相邻的，那么对应顶点之间就有边。若一步从 \((r,c)\) 走到邻居 \((r',c')\)，那么这一步的代价定义为目标单元的权值 \(M_{r',c'}\)。在这个约定下，路径
$$P=((r_0,c_0),(r_1,c_1),\dots,(r_k,c_k))$$
的总代价是
$$\operatorname{cost}(P)=M_{r_0,c_0}+\sum_{t=1}^{k} M_{r_t,c_t}=\sum_{t=0}^{k} M_{r_t,c_t}.$$
于是，Project Euler 83 就被精确地转化成了一个从起点顶点到终点顶点的最短路径问题。
矩阵中所有数都是正整数，所以所有有向边的权重也都是正的。这一点非常关键。第一，任何包含回路的路径，只要把这个回路删掉，总代价就会更小，因此最优路径不需要重复访问某个单元。第二，Dijkstra 算法之所以能够贪心地“先固定当前最小者”，正是建立在边权非负且这里更强地为正的前提之上。
最小代价函数满足
$$d(0,0)=M_{0,0},$$
而对其他任意单元都有
$$d(r,c)=M_{r,c}+\min_{(u,v)\in \mathcal{N}(r,c)} d(u,v),$$
其中 \(\mathcal{N}(r,c)\) 表示 \((r,c)\) 在矩阵内部的正交邻居集合。
这个式子给出了正确的最优子结构：到达 \((r,c)\) 的最后一步必然来自某个邻居。但问题在于，这些方程不是按某种天然顺序独立展开的，而是彼此耦合。比如 \(d(r,c)\) 可能依赖 \(d(r,c+1)\)，而 \(d(r,c+1)\) 又可能通过另一条路线反过来依赖 \(d(r,c)\)。这种反馈环正是本题不能像 Problem 81 或 Problem 82 那样用一次简单 DP 扫描解决的原因。
Dijkstra 算法会为每个单元维护一个当前已知的最小暂定值，并用一个最小优先队列保存候选状态。每当队列中暂定值最小的单元被取出时，这个值就已经是最终最优值。对某个邻居 \((r',c')\) 的松弛公式是
$$\text{candidate}=d(r,c)+M_{r',c'}.$$
如果这个候选值小于该邻居目前记录的最好结果，就更新它并把新的状态放入优先队列。
正确性证明沿用正权最短路的经典论证。假设存在一个被取出的单元，它是第一个“暂定值大于真实最优值”的错误取出。沿着一条真正最优的到达路径，考虑其中第一个尚未被取出的单元，以及它在该路径上的前驱。前驱既然已经更早被取出，就必然是以正确最优值取出的；那么在处理前驱时，下一条边的松弛就会把一个不大于终点真实最优值的候选数压入队列。这与“当前这个错误单元是第一个被错误取出的最小者”矛盾。因此，每个被取出的单元都会被正确地最终确定，终点也不例外。
实现中用于校验的样例矩阵是
$$\begin{pmatrix} 131 & 673 & 234 & 103 & 18 \\ 201 & 96 & 342 & 965 & 150 \\ 630 & 803 & 746 & 422 & 111 \\ 537 & 699 & 497 & 121 & 956 \\ 805 & 732 & 524 & 37 & 331 \end{pmatrix}.$$
其中一条最优路径为
$$(0,0)\to(1,0)\to(1,1)\to(1,2)\to(0,2)\to(0,3)\to(0,4)\to(1,4)\to(2,4)\to(2,3)\to(3,3)\to(4,3)\to(4,4).$$
对应总代价是
$$131+201+96+342+234+103+18+150+111+422+121+37+331=2297.$$
这里从 \((1,2)\) 向上回到 \((0,2)\) 的那一步非常说明问题：最优路径并不是单调向右下推进的。只要这一点成立，原来那种只按右和下展开的动态规划就已经不够用了。
C++、Python 和 Java 的实现都先读入矩阵，建立一个二维距离表，并把除起点外的所有位置初始化为无穷大。优先队列首先压入起点状态，其代价就是左上角单元本身的数值。
随后三份实现都执行同一个主循环：取出当前暂定代价最小的状态，如果这个队列条目已经过期，就直接跳过；否则尝试四个正交邻居。只要进入某个邻居会得到更小的总代价，就更新距离表，并把新的状态再次压入队列。这就是 Dijkstra 的惰性堆实现方式：没有显式的 decrease-key 操作，旧条目等到将来再次弹出时再丢弃即可。
三种语言之间只存在表达层面的差别。C++ 版本还会先验证标准 \(5\times5\) 样例，并且在终点单元被弹出时就可以立刻返回；Python 和 Java 版本则把同样的松弛过程继续执行到优先队列清空。无论哪一种，最后输出的都是右下角单元已经最终确定的最短距离。
若矩阵有 \(R\) 行、\(C\) 列，则图中共有 \(V=RC\) 个顶点，最多有 \(E\le 4RC\) 次面向邻居的有向松弛。使用二叉堆时，Dijkstra 的时间复杂度为
$$O(E\log V)=O(RC\log(RC)).$$
对于 \(n\times n\) 方阵，这可以写成 \(O(n^2\log n)\)，因为 \(\log(n^2)=2\log n\)。
距离表需要 \(O(RC)\) 空间；优先队列即使包含惰性更新带来的常数倍重复条目，总量也仍然保持在 \(O(RC)\) 级别。对实际的 \(80\times80\) 数据来说，这只对应 \(6400\) 个顶点和最多 \(25600\) 条邻接边，因此用普通堆实现最短路完全足够。
Дана матрица \(80\times80\) \(M\). Путь начинается в левой верхней клетке \((0,0)\), заканчивается в правой нижней клетке \((79,79)\) и на каждом шаге может двигаться вверх, вниз, влево или вправо, не выходя за границы матрицы. Стоимость пути равна сумме значений всех посещенных клеток, поэтому в ответ входят и стартовая, и конечная клетки.
Именно возможность двигаться во всех четырех направлениях отличает эту задачу от более ранних задач о сумме пути. Как только разрешены шаги влево и вверх, граф зависимостей между клетками содержит циклы, и уже нельзя найти такой фиксированный порядок обхода по строкам или столбцам, который делал бы однопроходный динамический алгоритм корректным.
Обозначим через \(d(r,c)\) минимальную возможную сумму по всем допустимым путям из \((0,0)\) в \((r,c)\). Именно эту величину и вычисляют реализации: они интерпретируют матрицу как взвешенный граф и затем запускают на нем алгоритм Дейкстры.
Каждая клетка рассматривается как вершина. Две вершины соединяются тогда и только тогда, когда соответствующие клетки являются ортогональными соседями в решетке. Если шаг идет из \((r,c)\) в соседнюю клетку \((r',c')\), то цена этого шага равна значению целевой клетки \(M_{r',c'}\). При таком соглашении путь
$$P=((r_0,c_0),(r_1,c_1),\dots,(r_k,c_k))$$
имеет суммарную стоимость
$$\operatorname{cost}(P)=M_{r_0,c_0}+\sum_{t=1}^{k} M_{r_t,c_t}=\sum_{t=0}^{k} M_{r_t,c_t}.$$
Следовательно, задача Project Euler в точности сводится к поиску кратчайшего пути от стартовой вершины к целевой.
Все элементы матрицы положительны, а значит, все ориентированные ребра тоже имеют положительный вес. Это важно по двум причинам. Во-первых, любой путь с циклом можно удешевить, если удалить этот цикл, так что оптимальному пути не нужно посещать одну и ту же клетку дважды. Во-вторых, именно положительность весов делает жадное правило извлечения в алгоритме Дейкстры корректным.
Функция минимальной стоимости удовлетворяет соотношениям
$$d(0,0)=M_{0,0},$$
а для любой другой клетки
$$d(r,c)=M_{r,c}+\min_{(u,v)\in \mathcal{N}(r,c)} d(u,v),$$
где \(\mathcal{N}(r,c)\) обозначает множество ортогональных соседей клетки \((r,c)\), остающихся внутри матрицы.
Это правильная формулировка оптимальной подструктуры: последний шаг в \((r,c)\) обязательно приходит из некоторой соседней клетки. Но проблема в том, что эти уравнения связаны между собой. Значение \(d(r,c)\) может зависеть от \(d(r,c+1)\), тогда как \(d(r,c+1)\) по другой траектории может снова зависеть от \(d(r,c)\). Именно эта циклическая обратная связь объясняет, почему для задач 81 и 82 существуют более простые динамические схемы, а для задачи 83 такой подход уже не проходит.
Алгоритм Дейкстры хранит для каждой клетки текущее лучшее найденное расстояние и минимальную приоритетную очередь кандидатных состояний. Когда из очереди извлекается клетка с наименьшим временным значением, это значение уже является окончательным. Шаг релаксации для соседа \((r',c')\) имеет вид
$$\text{candidate}=d(r,c)+M_{r',c'}.$$
Если этот кандидат лучше текущего известного результата для соседа, его нужно обновить.
Доказательство корректности стандартно для положительных весов. Предположим, что существует извлеченная клетка, которая является первой с временным значением больше истинного оптимума. Рассмотрим на действительно оптимальном пути к этой клетке первую еще не извлеченную клетку и ее предшественника на том же пути. Предшественник должен был быть извлечен раньше со своим правильным значением; значит, при релаксации следующего ребра в очередь попал бы кандидат, не превосходящий истинного оптимума конечной клетки. Это противоречит выбору рассматриваемой клетки как первой неправильной извлеченной вершины. Следовательно, каждая извлеченная клетка, включая цель, фиксируется правильно.
Проверочный пример, используемый в реализации, таков:
$$\begin{pmatrix} 131 & 673 & 234 & 103 & 18 \\ 201 & 96 & 342 & 965 & 150 \\ 630 & 803 & 746 & 422 & 111 \\ 537 & 699 & 497 & 121 & 956 \\ 805 & 732 & 524 & 37 & 331 \end{pmatrix}.$$
Один из оптимальных маршрутов равен
$$(0,0)\to(1,0)\to(1,1)\to(1,2)\to(0,2)\to(0,3)\to(0,4)\to(1,4)\to(2,4)\to(2,3)\to(3,3)\to(4,3)\to(4,4).$$
Его стоимость составляет
$$131+201+96+342+234+103+18+150+111+422+121+37+331=2297.$$
Подъем вверх из \((1,2)\) обратно в \((0,2)\) здесь и есть ключевая особенность: лучший путь не является монотонным. Уже этот единственный шаг показывает, почему динамики только вправо и вниз недостаточно.
Реализации на C++, Python и Java считывают матрицу, создают двумерную таблицу расстояний и заполняют ее бесконечностями, кроме стартовой клетки. В приоритетную очередь сначала помещается стартовое состояние, стоимость которого равна значению левой верхней клетки.
Далее выполняется один и тот же цикл: извлекается состояние с минимальной временной стоимостью, оно игнорируется, если запись в очереди уже устарела, и в противном случае проверяются все четыре ортогональных соседа. Если переход в соседа дает меньшую суммарную стоимость, новая дистанция сохраняется, а в очередь помещается свежая запись. Это ленивый вариант Дейкстры с кучей: явной операции уменьшения ключа нет, поэтому старые записи просто пропускаются, когда позже снова появляются на вершине очереди.
Различия между тремя языками касаются только формы записи. Реализация на C++ дополнительно проверяет стандартный пример \(5\times5\) и может завершиться сразу после извлечения целевой клетки; реализации на Python и Java продолжают тот же процесс релаксации до полного опустошения очереди. Во всех вариантах печатается уже окончательно найденное расстояние до правой нижней клетки.
Если у матрицы \(R\) строк и \(C\) столбцов, то граф содержит \(V=RC\) вершин и не более \(E\le 4RC\) направленных релаксаций к соседям. С двоичной кучей алгоритм Дейкстры работает за
$$O(E\log V)=O(RC\log(RC)).$$
Для квадратной решетки \(n\times n\) это равно \(O(n^2\log n)\), поскольку \(\log(n^2)=2\log n\).
Таблица расстояний требует \(O(RC)\) памяти; приоритетная очередь тоже остается в пределах \(O(RC)\), если считать лишь постоянный коэффициент из-за дубликатов в ленивой схеме обновлений. Для реального экземпляра \(80\times80\) это всего \(6400\) вершин и максимум \(25600\) соседних ребер, что очень мало для обычного heap-based вычисления кратчайшего пути.
لدينا مصفوفة \(80\times80\) نرمز لها بـ \(M\). يبدأ المسار من الخلية العلوية اليسرى \((0,0)\)، وينتهي عند الخلية السفلية اليمنى \((79,79)\)، ويجوز في كل خطوة التحرك إلى أعلى أو أسفل أو يسار أو يمين ما دام المسار يبقى داخل حدود المصفوفة. تكلفة المسار هي مجموع قيم جميع الخلايا التي يمر بها، ولذلك تدخل قيمة خلية البداية وقيمة خلية النهاية في المجموع.
السماح بالحركة في الاتجاهات الأربعة هو الفرق الجوهري بين هذه المسألة ومسائل path sum السابقة. فعندما تصبح الحركتان إلى اليسار وإلى الأعلى مسموحتين، يظهر في شبكة الاعتماد بين الخلايا دورات، وعندئذ لا يعود هناك ترتيب ثابت صفا بعد صف أو عمودا بعد عمود يجعل برمجة ديناميكية بتمرير واحد صحيحة.
لنرمز بـ \(d(r,c)\) إلى أصغر مجموع ممكن بين جميع المسارات الصحيحة من \((0,0)\) إلى \((r,c)\). هذا هو المقدار الذي تحسبه التطبيقات فعليا: فهي تحول المصفوفة إلى رسم بياني موزون ثم تطبق عليه خوارزمية ديكسترا.
نعد كل خلية رأسا في الرسم البياني. ويرتبط رأسان إذا كانت الخليتان المتقابلتان جارين متعامدين في الشبكة. وإذا انتقلنا من \((r,c)\) إلى جار \((r',c')\)، فإن تكلفة هذه الخطوة هي قيمة خلية الوصول \(M_{r',c'}\). وبهذا الاصطلاح يكون المسار
$$P=((r_0,c_0),(r_1,c_1),\dots,(r_k,c_k))$$
ذا تكلفة كلية
$$\operatorname{cost}(P)=M_{r_0,c_0}+\sum_{t=1}^{k} M_{r_t,c_t}=\sum_{t=0}^{k} M_{r_t,c_t}.$$
ومن ثم تصبح مسألة Project Euler 83 بالضبط مسألة أقصر مسار من رأس البداية إلى رأس النهاية.
كل عناصر المصفوفة موجبة، ولذلك فإن جميع أوزان الحواف الموجهة موجبة أيضا. وهذا مهم لسببين. الأول أن أي مسار يحتوي دورة يمكن تحسينه بحذف هذه الدورة، ولذلك لا يحتاج المسار الأمثل إلى زيارة خلية واحدة أكثر من مرة. والثاني أن صحة الاختيار الجشع في خوارزمية ديكسترا تعتمد أصلا على كون الأوزان غير سالبة، وهنا هي موجبة بالفعل.
تحقق دالة الكلفة الدنيا العلاقتين
$$d(0,0)=M_{0,0},$$
ولكل خلية أخرى
$$d(r,c)=M_{r,c}+\min_{(u,v)\in \mathcal{N}(r,c)} d(u,v),$$
حيث تمثل \(\mathcal{N}(r,c)\) مجموعة الجيران المتعامدين للخلية \((r,c)\) داخل حدود المصفوفة.
هذه هي صياغة البنية المثلى الصحيحة: فالخطوة الأخيرة إلى \((r,c)\) لا بد أن تأتي من إحدى الخلايا المجاورة. لكن الصعوبة أن هذه المعادلات مترابطة وليست أحادية الاتجاه. فقد يعتمد \(d(r,c)\) على \(d(r,c+1)\)، بينما قد يعتمد \(d(r,c+1)\) مرة أخرى على \(d(r,c)\) عبر مسار آخر. هذه الحلقة من الاعتماد المتبادل هي السبب المباشر في أن Problem 83 لا يقبل نفس البرمجة الديناميكية البسيطة التي كانت تكفي في Problem 81 و Problem 82.
تحفظ خوارزمية ديكسترا لكل خلية مسافة مبدئية أفضل ما عثر عليه حتى اللحظة، كما تحفظ حالات مرشحة داخل طابور أولوية من النوع الأصغر أولا. وكلما أخرجنا الخلية ذات أصغر قيمة مبدئية، كانت تلك القيمة قد أصبحت نهائية بالفعل. أما خطوة الإرخاء لجار \((r',c')\) فهي
$$\text{candidate}=d(r,c)+M_{r',c'}.$$
فإذا كانت هذه القيمة المرشحة أصغر من أفضل قيمة معروفة حاليا لذلك الجار، وجب تحديثه وإدخال الحالة الجديدة في طابور الأولوية.
برهان الصحة هو البرهان القياسي للأوزان الموجبة. افترض أن هناك خلية أخرجت من الطابور، وكانت أول خلية تكون قيمتها المبدئية أكبر من القيمة المثلى الحقيقية. انظر على مسار حقيقي أمثل يؤدي إلى هذه الخلية إلى أول خلية لم تكن قد أخرجت بعد، ثم إلى سابقتها على المسار نفسه. لا بد أن السابقة قد أخرجت من قبل بقيمتها الصحيحة، وعند إرخاء الحافة التالية كان ينبغي إدخال قيمة مرشحة لا تتجاوز القيمة المثلى الحقيقية للخلية النهائية. وهذا يناقض افتراض أننا أمام أول استخراج خاطئ. إذن كل خلية تخرج من الطابور تثبت قيمتها الصحيحة، بما في ذلك خلية الهدف.
المثال الذي تستخدمه الشيفرة للتحقق هو
$$\begin{pmatrix} 131 & 673 & 234 & 103 & 18 \\ 201 & 96 & 342 & 965 & 150 \\ 630 & 803 & 746 & 422 & 111 \\ 537 & 699 & 497 & 121 & 956 \\ 805 & 732 & 524 & 37 & 331 \end{pmatrix}.$$
ومن المسارات المثلى فيه
$$(0,0)\to(1,0)\to(1,1)\to(1,2)\to(0,2)\to(0,3)\to(0,4)\to(1,4)\to(2,4)\to(2,3)\to(3,3)\to(4,3)\to(4,4).$$
وتكون كلفته
$$131+201+96+342+234+103+18+150+111+422+121+37+331=2297.$$
الخطوة الصاعدة من \((1,2)\) إلى \((0,2)\) هي التفصيلة الحاسمة هنا: أفضل مسار ليس أحادي الاتجاه. وهذه الخطوة وحدها تكفي لتوضيح لماذا لا تصلح برمجة ديناميكية مقيدة بالحركة إلى اليمين والأسفل فقط.
تقرأ تطبيقات C++ و Python و Java المصفوفة، ثم تبني جدولا ثنائيا للمسافات وتملأه بقيمة لا نهائية في كل المواضع ما عدا خلية البداية. بعد ذلك يوضع في طابور الأولوية وضع البداية، وتكون كلفته مساوية لقيمة الخلية العلوية اليسرى نفسها.
ثم تتكرر الحلقة نفسها: استخراج الحالة ذات الكلفة المبدئية الأصغر، وتجاهلها إذا كانت هذه النسخة قديمة، وإلا فحص الجيران الأربعة المتعامدين. وكلما أعطى الدخول إلى جار ما مجموعا أصغر، تسجل الشيفرة المسافة الأفضل وتضيف حالة جديدة إلى الطابور. هذا هو الأسلوب الكسول في ديكسترا المعتمد على heap: لا توجد عملية صريحة لتقليل المفتاح، وإنما تترك الإدخالات القديمة حتى تظهر لاحقا ثم تتجاوز.
الاختلاف بين اللغات الثلاث يقتصر على تفاصيل العرض. فنسخة C++ تتحقق كذلك من المثال القياسي \(5\times5\) ويمكنها التوقف بمجرد استخراج خلية الهدف، بينما تواصل نسختا Python و Java عملية الإرخاء نفسها حتى يفرغ الطابور تماما. وفي جميع الحالات تكون القيمة المطبوعة هي المسافة النهائية الصحيحة إلى الخلية السفلية اليمنى.
إذا كانت للمصفوفة \(R\) صفوف و \(C\) أعمدة، فإن الرسم البياني يحتوي \(V=RC\) رأسا، وبحد أقصى \(E\le 4RC\) عملية إرخاء موجهة نحو الجيران. ومع heap ثنائي تكون كلفة ديكسترا الزمنية
$$O(E\log V)=O(RC\log(RC)).$$
وفي شبكة مربعة \(n\times n\) يصبح ذلك \(O(n^2\log n)\)، لأن \(\log(n^2)=2\log n\).
أما الذاكرة فهي \(O(RC)\) لجدول المسافات، ويبقى طابور الأولوية أيضا ضمن \(O(RC)\) إذا تجاهلنا عاملا ثابتا ناتجا عن التكرارات التي يسببها التحديث الكسول. وفي الحالة الفعلية \(80\times80\) لا نتعامل إلا مع \(6400\) رأسا وبحد أقصى \(25600\) حافة جوار، وهو حجم صغير جدا بالنسبة إلى حساب قياسي لأقصر المسارات باستخدام heap.