Если дугам приписаны стоимости dij, то стоимость остовного дерева определяется как сумма dijпо всем дугам дерева. Остовное дерево с наименьшей стоимостью среди всех остовных деревьев называется минимальным остовным деревом.
Замечание 3. В общем случае минимальное остовное дерево отличается от дерева кратчайших путей.
Следующие две леммы кажутся очевидными, однако их доказательства требуют внимательного изучения.
Лемма 1.Пусть Va— произвольный узел и еах — кратчайшая дуга среди всех дуг, смежных с Va. Тогда существует минимальное остовное дерево Т*, содержащее дугу еах.
Доказательство. Пусть Т — минимальное остовное дерево, а, А — подмножество дуг, смежных с Va, например, А = {eab, eac, ead, eax}. Предположим, что дуга еахявляется кратчайшей дугой, смежной с Va, но не принадлежит Т. Поскольку Т — остовное дерево, то в Т должен быть путь из Vxв Va, содержащий одну из дуг А, например, ead. Обозначим этот путь через (Pxd, eda), где Pxd— путь из Vx в Vd . Заменяя eadна еах, получим Т*. Если еахкороче, чем ead, то заключаем, что Т* — остовное дерево с меньшей стоимостью.
Во-первых, в дереве Т* Vaсоединяется с Vxдугой еах, а с узлом Vd – путем (eax,Pxd). Оставшиеся узлы Vb, Vcпо-прежнему связаны с Vaи, следовательно, с остальными узлами сети, значит, Т* является остовным деревом.
Во-вторых, стоимость Т* меньше, чем Т, так как еахкороче, чем ead. Это противоречит предположению о том, что Т — минимальное остовное дерево. Если дуги eadи еахимеют одинаковые длины, то также можно заменить еаdна еахи получить минимальное остовное дерево Т*, содержащее еах.
Лемма 2.Если известно, что подмножество ребер, образующих поддерево F, является частью минимального остовного дерева, то существует минимальное остовное дерево, содержащее F, и минимальное ребро, соединяющее F u N-F.
Доказательство. Доказательство в точности совпадает с доказательством леммы 1, если заменить Vaна F.
По лемме 1 можно начать из произвольной вершины и выбрать наименьшую смежную дугу. Так как известно, что только что выбранная дуга является частью минимального остовного дерева, то можно в лемме 2 взять ее в качестве F и выбрать наименьшую дугу, инцидентную F.
Можно продолжить выбор наименьшего ребра, инцидентного уже выбранной компоненте. Это алгоритм Прима для нахождения минимального остовного дерева.
Идея алгоритма следующая. Алгоритм создает последовательные связные поддеревья, путем присоединения на каждом шаге одной смежной дуги так, чтобы на каждой стадии была выбрана инциндентная дуга с самой маленькой стоимостью. Пример реализации идеи алгоритма Прима представлен на рис. 12. Если начальный узел V0, то последовательность присоединяемых дуг следующая: дуга со стоимостью 1, смежная (вертикальная) дуга со стоимостью 2, дуга (горизонтальная) со стоимостью 2, дуга со стоимостью 4, дуга со стоимостью 3. Стоимость минимального остовного дерева 12.
Рис. 12. Пример минимального остовного дерева
Замечание 4. Алгоритм Прима для минимального остовного дерева сходен с алгоритмом Дейкстры для нахождения кратчайших путей.