Дейкстра на матрице смежности за O(V²) — когда это лучше, чем версия на куче?

Версия без кучи: на каждом из V шагов линейным проходом ищем ещё не закрытую вершину с минимальным dist, фиксируем её и релаксируем соседей. Никакой кучи.

vector<ll> dist(n, INF);
vector<bool> used(n, false);
dist[s] = 0;
for (int iter = 0; iter < n; iter++) {
    int v = -1;
    for (int i = 0; i < n; i++)
        if (!used[i] && (v == -1 || dist[i] < dist[v])) v = i;
    if (dist[v] == INF) break;
    used[v] = true;
    for (int u = 0; u < n; u++)
        if (g[v][u] != INF && dist[v] + g[v][u] < dist[u])
            dist[u] = dist[v] + g[v][u];
}

Сложность O(V²) по времени. Это выгоднее версии на куче O(E log V), когда граф плотный: при E ≈ V² куча даёт O(V² log V), а квадратичная версия — чистый O(V²). Грубое правило: плотный граф (E близко к V²) → O(V²) без кучи; разреженный (E ≈ V) → куча.