FasterHarder: В общем понял (прочитав в одном материале), что надо напрочь отказываться от весовой матрицы и переходить на список смежности.
Колоссальной оптимизации можно добиться, если построить список смежности, упорядочив внутри по весу по неубыванию...

На рис.показал, что из себя будет представлять такой список смежности (один из вариантов реализации, далеко не факт, что оптимальный):
_______________________________.png (, : 8)

То есть, если подается на вход весовая матрица (например, считыванием из файла + с клавиатуры обычно не вводят весовые матрицы - неудобно абсолютно+долго), то строим список смежности, добавляя по блоку информации в нужный ЛОС, не теряя при этом отсортированности. По факту возможны 3 операции вставки в ЛОС: в начало, в конец и в "средину". Придется каждую из них программить, эх...итоговая программа вообще разрастется уже до 300+ строк кода

Если происходит ввод с клавиатуры, то требуем формат: <1ая смежная вершина> <2ая смежная вершина> <вес ребра между ними>, то есть 3 числа. И также после этого происходит добавление в таблицу списка смежности, не теряя упорядоченности.

Получив "отсортированный" список смежности, операция поиска минимального веса будет выполняться за время O(n) (n - кол-во вершин графа). Это может в "миллиарды" раз ускорить алгоритм). Правда после этого, надо производить удаление соответствующего узла из начало списка + ведь еще придется удалить симметричного близнеца(!), который будет стоять не в начале списка. Вот эта перестройка списка смежности может быть не оч.быстрой, хотя...

Также благодаря списку смежности и удалению узлов в конце концов может не остаться ни одного элемента в конкретном ЛОС - и это замечательно, в этом случае вершина больше вообще не участвует в обработке (об этом писал ранее).

Единственный момент, если обрабатывается ПОЛНЫЙ ГРАФ, то вроде в этом случае нецелесообразно вообще получать список смежности, хотя...Ведь на построение уйдет кучу времени, но потом это будет окупаться при поиске наименьшего. Здесь непонятка, стоит ли овчинка выделки. С др.стороны ведь неизвестно, какого типа подается на вход граф и надо убедиться, что он является полным + очевидно, что в 99.99% граф будет подаваться неполным, поэтому, независимо от конфигурации графа (полный, разреженный, плотный и пр.) надо всегда получать список смежности и это ДОЛЖНО РЕЗКО увеличить производительность выполнения прожки, вроде)

p.s. тут сплошная динамика и все это надо закодить корректно и будет несколько сотен строк кода...в их примерчиках по 25-30 строк, правда 19 программ из 20, которые я видел были на С++ (в связке с СТЛ-кой приблудой) + на весовых матрицах (без построения списка смежности). Пусть попробуют на Си покодить, создавая с нуля велосипеды))

https://forum.sources.ru/index.php?showtopic=421519&view=findpost&p=3848139