Задача: Имеется [latex]n [/latex] городов. Некоторые из них соединены дорогами известной длины. Вся система дорог задана квадратной матрицей порядка [latex]n [/latex], элемент [latex]a_{ij} [/latex] которой равен некоторому отрицательному числу, если город [latex]i [/latex] не соединен напрямую дорогой с городом [latex]j [/latex] и равен длине дороги в противном случае latex [/latex].
- Для 1-го города найти кратчайшие маршруты в остальные города.
- В предположении, что каждый город соединен напрямую с каждым, найти кратчайший маршрут, начинающийся в 1-м городе и проходящий через все остальные города.
Входные данные:
| 4 |
| -1 | 2 | 4 | -1 |
| 2 | -1 | 1 | 6 |
| 4 | 1 | -1 | 1 |
| -1 | 6 | 1 | -1 |
Выходные данные:
1 > 2 = 2
1 > 3 = 3
1 > 4 = 4
Длина кратчайшей цепи, проходящей через все вершины 4
Ссылка на ideone: http://ideone.com/iXjoLZ
Решение:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include <iostream> #include <climits> using namespace std; int main(){ int n,st=0,sum=0; bool p=true; cin>>n; int GR[n][n]; int distance[n]; bool visited[n]; int index; for (int i=0; i<n; i++){ distance[i]=INT_MAX; visited[i]=false; for (int j=0; j<n; j++){ cin>>GR[i][j]; if (GR[i][j]<0 && i!=j)p=false; } } if (p==true){ for (int i=0; i<n-1; i++){ int minl=INT_MAX; for (int j=0; j<n; j++){ if (GR[i][j]<minl && GR[i][j]>0 && j>i) minl=GR[i][j]; } sum+=minl; } } distance[st]=0; for (int p=0; p<n-1; p++){ int min=INT_MAX; for (int i=0; i<n; i++){ if (!visited[i] && distance[i]<min){ min=distance[i]; index=i; } } visited[index]=true; for (int i=0; i<n; i++){ if (!visited[i] && GR[index][i]>0 && distance[index]!=INT_MAX && distance[index]+GR[index][i]<distance[i]){ distance[i]=distance[index]+GR[index][i]; } } } for (int i=1; i<n; i++){ if (distance[i]!=INT_MAX) cout<<st+1<<" > "<<i+1<<" = "<<distance[i]<<endl; else cout<<st+1<<" > "<<i+1<<" = "<<"Маршрут недоступен"<<endl; } if (p==true) cout<<"Длина кратчайшей цепи, проходящей через все вершины "<<sum; else cout<<"Не все вершины графа соединены"; } |
Алгоритм: Для решения задачи применим алгоритм Дейкстры. Применяя этот алгоритм мы считаем что у нас нету ребер с отрицательным весом. Если вес ребра отрицательный, то его просто не существует (по условию задачи). Вводим матрицу смежности графа и проверяем является ли граф полным (для задания 2). Если граф является полным, то ищем для каждой вершины инцидентное ребро с минимальным весом и суммируем (задание 2). В цикле каждой вершине присваиваем минимально расстояние до нее от первой вершины и записываем в массив (задание 1).