Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <stdio.h>
- #define INF 10000
- int find_min(int S[15], int D[15], int N);
- int main()
- {
- int i, j, k, tmp;
- int N = 15; //Количество вершин
- int matrix[15][15] = //Матрица смежности
- { {INF, 15, INF, INF, INF, INF, INF, INF, 10, 50, INF, INF, INF, INF, INF},
- {INF, INF, 20, 10, 30, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
- {INF, INF, INF, INF, INF, 40, INF, INF, INF, INF, INF, INF, INF, INF, INF},
- {INF, INF, INF, INF, 60, INF, INF, INF, 50, INF, INF, INF, INF, INF, INF},
- {INF, INF, INF, INF, INF, INF, 5, INF, INF, INF, INF, INF, INF, INF, INF},
- {INF, INF, INF, INF, INF, INF, 10, INF, INF, INF, INF, INF, INF, INF, INF},
- {INF, INF, INF, INF, INF, INF, INF, 10, INF, INF, INF, INF, INF, INF, INF},
- {INF, INF, INF, INF, INF, INF, INF, INF, INF, 25, 5, INF, INF, INF, INF},
- {INF, INF, INF, INF, INF, INF, INF, 15, INF, INF, INF, INF, INF, INF, INF},
- {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 15, INF, INF},
- {INF, INF, INF, INF, INF, INF, INF, INF, INF, 45, INF, INF, INF, INF, INF},
- {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 15, INF, INF, INF, INF},
- {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 35, INF, 30, INF},
- {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 40},
- {10, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF}};
- int nu, target;
- int S[15] = { 0 };
- int D[15] = { 0 };
- //int P[15];
- /*for (i = 1; i < N; i++)
- {
- P[i] = -1;
- }*/
- //Вывод матрицы смежности
- for (i = 0; i < N; i++)
- {
- printf("\t%d", i + 1);
- }
- printf("\n");
- for (i = 0; i < N; i++)
- {
- printf("%d\t", i + 1);
- for (j = 0; j < N; j++)
- {
- tmp = (matrix[i][j] == INF) ? 0 : matrix[i][j];
- printf("%d\t", tmp);
- }
- printf("\n");
- }
- printf("Dijkstra's algorithm:\n");
- printf("Enter start vertex nu: ");
- scanf("%d", &nu);
- printf("Enter target vertex: ");
- scanf("%d", &target);
- S[nu - 1] = 1; //Включаем вершину nu в S
- for (i = 0; i < N; i++) //Инициализируем D
- {
- if (i == nu - 1)
- {
- D[i] = 0;
- continue;
- }
- D[i] = matrix[nu - 1][i];
- }
- //P[0] = nu - 1;
- //k = 1;
- for (i = 0; i < N; i++)
- {
- tmp = find_min(S, D, N); //Очередная вершина
- if (tmp < 0) break;
- S[tmp] = 1;
- for (j = 0; j < N; j++)
- {
- if (S[j] == 1) continue;
- D[j] = (D[j] < D[tmp] + matrix[tmp][j]) ? D[j] : D[tmp] + matrix[tmp][j];
- /*if (D[j] >= D[tmp] + matrix[tmp][j])
- {
- P[k] = tmp;
- }*/
- }
- //k++;
- }
- for (i = 0; i < N; i++)
- {
- printf("Shortest route from %d to %d is %d\n", nu, i + 1, D[i]);
- }
- /*for (i = 0; i < k; i++)
- {
- if (P[i] == -1) continue;
- printf("%d ", P[i] + 1);
- }*/
- printf("Prima's algorithm\n");
- //Делаем граф неориентированным
- for (i = 0; i < N; i++)
- {
- for (j = 0; j <= i; j++)
- {
- tmp = matrix[i][j];
- if (tmp == INF) tmp = 0;
- if (tmp < matrix[j][i] && matrix[j][i] != INF) tmp = matrix[j][i];
- matrix[i][j] = tmp;
- matrix[j][i] = tmp;
- }
- }
- //Вывод матрицы смежности
- for (i = 0; i < N; i++)
- {
- printf("\t%d", i + 1);
- }
- printf("\n");
- for (i = 0; i < N; i++)
- {
- printf("%d\t", i + 1);
- for (j = 0; j < N; j++)
- {
- tmp = (matrix[i][j] == INF) ? 0 : matrix[i][j];
- printf("%d\t", tmp);
- }
- printf("\n");
- }
- int U[15] = { 0 };
- int result[15][15] = { 0 };
- int min = INF, start_index = -1, end_index = -1;
- printf("Enter start vertex: ");
- scanf("%d", &nu);
- U[nu - 1] = 1; //Выбираем вершину nu
- for(k = 0; k < N; k++)
- {
- for (i = 0; i < N; i++)
- {
- if (U[i] == 1)
- {
- for (j = 0; j < N; j++)
- {
- if (U[j] != 1 && matrix[i][j] != 0 && matrix[i][j] < min)
- {
- min = matrix[i][j];
- start_index = i;
- end_index = j;
- }
- }
- }
- }
- if (start_index != -1 && end_index != -1)
- {
- result[start_index][end_index] = min;
- result[end_index][start_index] = min;
- U[end_index] = 1;
- min = INF;
- start_index = -1;
- end_index = -1;
- }
- }
- printf("Tree:\n");
- for (i = 0; i < N; i++)
- {
- printf("\t%d", i + 1);
- }
- printf("\n");
- for (i = 0; i < N; i++)
- {
- printf("%d\t", i + 1);
- for (j = 0; j < N; j++)
- {
- tmp = (result[i][j] == INF) ? 0 : result[i][j];
- printf("%d\t", tmp);
- }
- printf("\n");
- }
- return 0;
- }
- int find_min(int S[15], int D[15], int N)
- {
- int result = -1;
- int min = INF;
- int i;
- for (i = 0; i < N; i++)
- {
- if (S[i] == 1) continue;
- if (D[i] < min)
- {
- min = D[i];
- result = i;
- }
- }
- return result;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement