Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //---------------------------------------------------------------------------
- //Алгоритм Дейкстры.поиска кратчайшего пути
- #include "stdafx.h"
- #include <iostream>
- #include <conio.h>
- #define VERTEXES 9 //Число вершин в графе
- using namespace std;
- class Graph {
- public:
- int v;
- int infinity = 1000; // Бесконечность
- int p = VERTEXES; // Количество вершин в графе
- int a[VERTEXES][VERTEXES] =
- {
- 0, 1, 0, 0, 0, 0, 0, 0, 0,
- 1, 0, 1, 0, 0, 1, 0, 0, 0,
- 0, 1, 0, 1, 1, 0, 0, 0, 0,
- 0, 0, 1, 0, 0, 1, 1, 0, 1,
- 0, 0, 1, 0, 0, 1, 1, 1, 0,
- 0, 1, 0, 1, 1, 0, 0, 0, 0,
- 0, 0, 0, 1, 1, 0, 0, 1, 1,
- 0, 0, 0, 0, 1, 0, 1, 0, 1,
- 0, 0, 0, 1, 0, 0, 1, 1, 0,
- };
- // Будем искать путь из вершины s в вершину g
- int s=0; // Номер исходной вершины
- int g=VERTEXES-1; // Номер конечной вершины
- int x[VERTEXES]; //Массив, содержащий единицы и нули для каждой вершины,
- // x[i]=0 - еще не найден кратчайший путь в i-ю вершину,
- // x[i]=1 - кратчайший путь в i-ю вершину уже найден
- int t[VERTEXES]; //t[i] - длина кратчайшего пути от вершины s в i
- int h[VERTEXES]; //h[i] - вершина, предшествующая i-й вершине
- // на кратчайшем пути
- bool excludePoints = false;
- // Инициализируем начальные значения массивов
- int u; // Счетчик вершин
- void ShortestWay(){
- for (u = 0; u < p; u++)
- {
- t[u] = infinity; //Сначала все кратчайшие пути из s в i
- //равны бесконечности
- x[u] = 0; // и нет кратчайшего пути ни для одной вершины
- }
- h[s] = 0; // s - начало пути, поэтому этой вершине ничего не предшествует
- t[s] = 0; // Кратчайший путь из s в s равен 0
- x[s] = 1; // Для вершины s найден кратчайший путь
- v = s; // Делаем s текущей вершиной
- while (1)
- {
- // Перебираем все вершины, смежные v, и ищем для них кратчайший путь
- for (u = 0; u < p; u++)
- {
- if (a[v][u] == 0) continue; // Вершины u и v несмежные
- if (x[u] == 0 && t[u] > t[v] + a[v][u]) //Если для вершины u еще не
- //найден кратчайший путь
- // и новый путь в u короче чем
- //старый, то
- {
- t[u] = t[v] + a[v][u]; //запоминаем более короткую длину пути в
- //массив t и
- h[u] = v; //запоминаем, что v->u часть кратчайшего
- //пути из s->u
- }
- }
- // Ищем из всех длин некратчайших путей самый короткий
- int w = infinity; // Для поиска самого короткого пути
- v = -1; // В конце поиска v - вершина, в которую будет
- // найден новый кратчайший путь. Она станет
- // текущей вершиной
- for (u = 0; u < p; u++) // Перебираем все вершины.
- {
- if (x[u] == 0 && t[u] < w) // Если для вершины не найден кратчайший
- // путь и если длина пути в вершину u меньше
- // уже найденной, то
- {
- v = u; // текущей вершиной становится u-я вершина
- w = t[u];
- }
- }
- if (v == -1)
- {
- cout << "Нет пути из вершины " << s << " в вершину " << g << "." << endl;
- break;
- }
- if (v == g) // Найден кратчайший путь,
- { // выводим его
- cout << "Кратчайший путь из вершины " << s << " в вершину " << g << ":";
- u = g;
- while (u != s)
- {
- cout << " " << u;
- u = h[u];
- }
- cout << " " << s << ". Длина пути - " << t[g];
- break;
- }
- x[v] = 1;
- } }
- void LongestWay() {}
- void Exclude() {
- int i, j, k;
- for (i = 0; i < VERTEXES; i++) {
- for (j = 0; j < VERTEXES; j++) {
- cout << a[i][j] << " ";
- }
- cout << endl;
- }
- int exc_num;
- cout << "How many points be excluded: "; cin >> exc_num; cout << endl;
- int *exc = new int[exc_num];
- for (k = 0; k < exc_num; k++) {
- cout << "Enter point #" << k << ": "; cin >> exc[k];
- }
- for (k = 0; k < exc_num; k++) {
- for (j = 0; j < VERTEXES; j++) {
- a[exc[k]][j] = 0;
- }
- for (i = 0; i < VERTEXES; i++) {
- a[i][exc[k]] = 0;
- }
- }
- for (i = 0; i < VERTEXES; i++) {
- for (j = 0; j < VERTEXES; j++) {
- cout << a[i][j] << " ";
- }
- cout << endl;
- }
- }
- void Choose() {
- int i, j, k;
- for (i = 0; i < VERTEXES; i++) {
- for (j = 0; j < VERTEXES; j++) {
- cout << a[i][j] << " ";
- }
- cout << endl;
- }
- int exc_num;
- cout << "How many points be choosen: "; cin >> exc_num; cout << endl;
- int *exc = new int[exc_num];
- for (k = 0; k < exc_num; k++) {
- cout << "Enter point #" << k << ": "; cin >> exc[k];
- }
- // Зануление ненужных
- for (k = 0; k < exc_num; k++) {
- if ((std::count(exc, exc + sizeof(exc) / sizeof(*exc), exc[k])) != 1) {
- cout << exc[k] << "\t" << (std::count(exc, exc + sizeof(exc) / sizeof(*exc), exc[k])) << endl;;
- /* for (j = 0; j < VERTEXES; j++) {
- //a[exc[k]][j] = 0;
- }
- for (i = 0; i < VERTEXES; i++) {
- //a[i][exc[k]] = 0;
- }*/
- }
- else continue;
- }
- cout << endl << endl;
- // Вывод конечной матрицы
- for (i = 0; i < VERTEXES; i++) {
- for (j = 0; j < VERTEXES; j++) {
- cout << a[i][j] << " ";
- }
- cout << endl;
- }
- }
- };
- int main()
- {
- setlocale(LC_ALL, "Russian");
- system("cls");
- cout << "1. Only find shortest way\n";
- cout << "2. Only find longest way\n";
- cout << "3. Exclude points from the way and find shortest way\n";
- cout << "4. Exclude points from the way and find longest way\n";
- cout << "5. Use only choosen points and find shortest way\n";
- cout << "6. Use only choosen points and find longest way\n";
- int N;
- cin >> N;
- Graph findw;
- switch (N) {
- case 1: findw.ShortestWay(); break;
- //case 2: findw.LongestWay(); break;
- case 3: findw.Exclude(); findw.ShortestWay(); break;
- //case 4: findw.Exclude(); findw.LongestWay(); break;
- case 5: findw.Choose(); findw.ShortestWay(); break;
- //case 6: findw.Choose(); findw.LongestWay(); break;
- default:
- cout << "Wrong item.\n";
- break;
- }
- system("pause");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement