Имеется N городов. Для каждой пары городов (I,J) можно построить дорогу, соединяющую эти два города и не заходящие в другие города. Стоимость такой дороги A(I,J). Вне городов дороги не пересекаются. Алгоритм: #include <stdio.h> #include <conio.h> #define max_v 100000 #define min(x,y) ((x)<(y)?(x):(y)) int mass[100][100]; // матрица смежностей int i,j,N,M,W; int a,b,c; int start,end; int D[100]; // массив, который хранит минимальный путь int used[100]; int short_way (int start, int end); int main () { FILE *inp = fopen("Gf.txt","rt"); fscanf (inp,"%d %d", &N, &M); // количество узлов и ребер for ( i = 0 ; i < N ; i++) // присваиваем элементам матрицы максимальные значения for ( j = 0 ; j < N ; j++) { mass[i][j]=max_v; mass[j][i]=max_v; } for (i = 0; i < M; i ++ ) // заполняем матрицу значениями из файла { fscanf(inp,"%d %d %d",&a,&b,&c); mass[a][b]=c; mass[b][a]=c; } fclose (inp); printf("Enter the first and the last point: "); // пример : " 1 3 " : 1 - начало , 3 - конец пути scanf ("%d %d",&start,&end); printf ("\The shortest way is: %d\n", short_way(start,end) ); getch (); return 0; } int short_way (int start, int end) { /* используем алгоритм Дейкстры */ for ( i = 0 ; i < N ; i++) // заполняем массив, который отвечает за проход узла (если побывали в узле, то присваиваем 1, иначе 0) used[i]=0; for( i = 0 ; i < N ; i++) D[i] = mass[start][i]; // массив, который содержит кратчайший путь из заданной вершины в вершину с номером i used[start] = 1; // побывали в начальном узле for( i = 0 ; i < N-2 ; i++) { int min_v = 1000000; for (j = 0; j < N; j++ ) if (used[j]==0 && D[j]< min_v) // если еще не побывали в вершине j, и значение в вершине с номером j меньше, чем предыдущее значение, { min_v = D[j]; // min_v присваивам минимальное значение. W = j; // W - номер узла с наименьшим значением пути } used[W]=1; for( j = 0 ; j < N ; j++) if (used[j]==0) D[j]=min( D[j], D[W] + mass[W][j]); // выбираем минимальный путь } if (start == end) // если начальный узел является конечным, D[end]=0; // то путь равен 0 return D[end]; }
Ключевые слова:
алгоритм Дейкстры граф кратчайший путь
|
|||||||