Iv. Динамические структуры данных

for ( j = i+1; j < N; j ++ ) 

if ( Col[i] != Col[j] &&
// ищем самое короткое ребро, 
D[i][j] < Dmin ) {
// не образующее цикла 

Dmin = D[i][j]; 

iMin = i;
jMin = j; 
} 
 Reb[k].i = iMin;
// запомнить найденное ребро 
 Reb[k].j = jMin; 
 col_j = Col[jMin]; 
 for ( i = 0; i < N; i ++ )
// перекрасить все вершины, цвет 
if ( Col[i] == col_j )
// которых совпал с цветом
Col[i] = Col[iMin]; 
// вершины jMin

 } 
// здесь надо вывести найденные ребра 
} 

---

Программирование на языке Си
©
 К. Поляков, 1995-2009 
http://kpolyakov.narod.ru
35
Дополнительно можно рассчитывать общую длину выбранных ребер, но это не меняет принци-
пиально алгоритм. Этот алгоритм требует памяти порядка n
2
 (обозначается O(n
2
), то есть при 
увеличении n в 2 раза объем требуемой памяти увеличивается в 4 раза). Его временная слож-
ность – O(n
3
), то есть при увеличении n в 2 раза время вычислений увеличивается в 8 раз (на-
до просмотреть O(n
3
) чисел и сделать это n-1 раз). 
 
Кратчайший путь 
 Формулировка задачи 
Задача. Задана сеть дорог между населенными пунктами (часть из них могут иметь односто-
роннее движение). Требуется найти кратчайший путь между двумя заданными пунктами. 
Обычно задачу несколько расширяют и находят сразу кратчайшие пути от заданной вершины 
ко всем остальным. В терминах теории графов задача выглядит так: 
В сети, где часть дорог имеет одностороннее движение, найти кратчайшие пути от заданной 
вершины ко всем остальным.