Алгоритм поиска минимального расстояния между двумя вершинами в графе представленном в виде матрицы смежности

@anastasyi · Регистрация: 03.09.2021

Студворк — интернет-сервис помощи студентам

Добрый день всем! Подправьте код пожалуйста(возможно, некоторые нужные строчки кода закомментированы).
Задание звучит так:
Немного модифицировав алгоритм обхода DFS, напишите новый алгоритм поиска минимального расстояния между двумя вершинами в графе. Суть алгоритма заключается в том, что он проходит по всем возможным путям в графе и при попадании в целевую вершину, проверяет длину пути, через который он туда попал с текущим минимально выявленным расстоянием.

C++
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
Graph.h
 
 
#ifndef __GRAPH__
#define __GRAPH__
 
#define SIZE 10
 
class Graph {
    public:
        Graph();
        // добавление вершины
        void addVertex(int vnumber);
        // добавление ребра
        void addEdge(int v1, int v2, int weight);
        // удаление вершины
        void delVertex(int vnumber);
        // удаление ребра
        void delEdge(int v1, int v2);
        //поиск количества путей
        int findMinWayDFS(int from, int to);
        void depthInnerDFS(int start, int finish, int min_dist, int& path_length, bool visited[]);
        
        
    private:
        bool edgeExists(int v1, int v2);
        bool vertexExists(int v);
 
        int matrix[SIZE][SIZE]; // матрица смежности
         
        int vertexes[SIZE]; // хранилище вершин
        int vertexCount; // количество добавленных вершин
};
#endif

C++
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
 
Graph.cpp
 
#include "../headers/graph.h"
 
#define VERYBIGINT 1000000000
 
Graph::Graph() {
    for(int i=0;i < SIZE; i++)
      for(int j=0; j< SIZE; j++)
        matrix[i][j] = 0;
    vertexCount = 0;
}
// добавление вершины
void Graph::addVertex(int vnumber)
{
    vertexes[vertexCount] = vnumber;
    vertexCount++;
}
// добавление ребра
void Graph::addEdge(int v1, int v2, int weight)
{
    matrix[v1][v2] = weight;
    matrix[v2][v1] = weight;
}
// проверка существования ребра
bool Graph::edgeExists(int v1, int v2)
{
    return matrix[v1][v2] > 0;
}
// проверка существования вершины
bool Graph::vertexExists(int v)
{
    for(int i=0;i<vertexCount;i++)
       if(vertexes[i] == v)
          return true;
    return false;
}
 
void Graph::depthInnerDFS(int start, int finish, int min_dist, int& path_length, bool visited[])
{
    visited[start] = true; // помечаем как посещенную
    int min_dist = MAX_VALUE;
    //int sum = 0;
    if (start == finish)
    {
        /*for (int k = 0; k < SIZE; ++k)
        {
            if (visited[k] == true)
                path_length += k;
        }*/
        for (int i = 0; i < SIZE; ++i)
        {
            for (int j = 0; j < SIZE; ++j)
            {
                if (this->matrix[i][j] == finish) break;
                path_length += this->matrix[i][j];
            }
        }
    }
    if (path_length < min_dist)
    {
        //min_dist = path_length;
        path_length;
    }
    else
    {
        for (int i = 0; i < SIZE; i++)
        {
            if (edgeExists(start, i) && !visited[i])
                depthInnerDFS(i, finish, min_dist, path_length, visited);
            //depthInner(i, visited); // если существует ребро и вершина не посещалась, то пройдем по нему в смежную вершину
        }
    }
}
int Graph::findMinWayDFS(int from, int to)
{
    int start = from, finish = to, path_length = 0, min_dist = MAX_VALUE;
    bool visited[SIZE]; // список посещенных вершин
    ///int distances[SIZE];
    for (int i = 0; i < SIZE; i++)
        visited[i] = false; // инициализируем как непосещенные
    depthInnerDFS(start, finish, min_dist, path_length, visited);
    //depthInnerDFS(from, to, visited);
    return path_length;
}

@SmallEvil · 17.03.2023, 13:49

Через dfs, поиск в глубину - очень неэффективное решение.
И я прям немного оторопел ...
Как то так ?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void Graph::depthInnerDFS(int start, int finish, int dist, int& min_dist,  bool* visited)
{
    visited[start] = true; // помечаем как посещенную
    if (start == finish) // путь найден
        min_dist = std::min(dist, min_dist); // минимальный путь из минимального и текущего
    for (int i = 0; i < SIZE; i++)
            if (edgeExists(start, i) && !visited[i])
                depthInnerDFS(i, finish, dist+1, min_dist, visited);
    visited[start] = false;
}
int Graph::findMinWayDFS(int from, int to)
{
    int start = from, finish = to, min_dist = SIZE;
    bool visited[SIZE]; // список посещенных вершин
    for (int i = 0; i < SIZE; i++)
        visited[i] = false; // инициализируем как не посещенные
    depthInnerDFS(start, finish, 0, min_dist, visited);
    // если min_dist == SIZE - значит путь не найден
    // но мы принимаем что граф связный и вершины существуют
    return min_dist;
}

@anastasyi · 17.03.2023, 14:19 **[ТС]**

[nick]SmallEvil[/nick, не понятно почему(тестов не видно), но пишет не верно решено.

Добавлено через 2 минуты

Сообщение от SmallEvil

Через dfs, поиск в глубину - очень неэффективное решение.
И я прям немного оторопел ...
Как то так ?

Ну в задании такие условия. через dfs

@SmallEvil · 17.03.2023, 14:24

Возможно нужно искать количество вершин в пути, у меня длина пути = количеству ребер.

C++
1
depthInnerDFS(start, finish, 1, min_dist, visited);

@anastasyi · 17.03.2023, 15:02 **[ТС]**

SmallEvil, попробую додумать, спасибо)

Добавлено через 26 минут
SmallEvil, Вообще по идее, так и должно быть как у вас, не понимаю, в чем дело

@SmallEvil · 17.03.2023, 15:29

Может тут уже используется вес ребра как "расстояние" между вершинами.
ТЗ как будто "не доносили".

@anastasyi · 17.03.2023, 15:54 **[ТС]**

SmallEvil, Да.там очень коряво сформулированное задание...Методом подбора сидишь и тыкаешь. Собирается и отрабатывает у меня в ide,но не там где надо

Добавлено через 17 минут
SmallEvil,

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int Graph::findMinWayDFS(int from, int to)
{
    std::cout << from << to << std::endl;
    int start = from, finish = to, min_dist = SIZE;
    bool visited[SIZE]; // список посещенных вершин
    for (int i = 0; i < SIZE; i++)
        visited[i] = false; // инициализируем как не посещенные
    depthInnerDFS(start, finish, 0, min_dist, visited);
    // если min_dist == SIZE - значит путь не найден
    // но мы принимаем что граф связный и вершины существуют
   
 std::cout << min_dist << std::endl;
 return min_dist;
}

если сяутом в самом методе вывести данные скрытого теста, то выводит 3(from)4(to) и 2 (min_dist).Но это мало чем может помочь конечно

@SmallEvil · 17.03.2023, 17:27

Сообщение от anastasyi

то выводит 3(from)4(to) и 2 (min_dist).Но это мало чем может помочь конечно

В самом методе уже доступен весь граф.
Так же его выведите, найдите кратчайший путь от вершины 3 до 4.
У вас есть всего 3 варианта :
- количество ребер в пути, который есть (он не проходит)
- количество вершин (для этого ,как япоказал, передаем в DFS не 0 а 1)
- вес ребер пути (его так же легко посчитать).

Добавлено через 17 минут
Кажется я накосячил.
Ребра :

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Graph::depthInnerDFS(int start, int finish, int dist, int& min_dist,  bool* visited)
{
    visited[start] = true; // помечаем как посещенную
    if (start == finish) // путь найден
        min_dist = std::min(dist, min_dist); // минимальный путь из минимального и текущего
    else
       for (int i = 0; i < SIZE; i++)
           if (edgeExists(start, i) && !visited[i])
               depthInnerDFS(i, finish, dist+1, min_dist, visited);
    visited[start] = false;
}
int Graph::findMinWayDFS(int from, int to)
{
    int start = from, finish = to, min_dist = SIZE;
    bool visited[SIZE]; // список посещенных вершин
    for (int i = 0; i < SIZE; i++)
        visited[i] = false; // инициализируем как не посещенные
    depthInnerDFS(start, finish, 0, min_dist, visited);
    // если min_dist == SIZE - значит путь не найден
    // но мы принимаем что граф связный и вершины существуют
    return min_dist;
}

Добавлено через 2 минуты
По весам ребер :

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Graph::depthInnerDFS(int start, int finish, int dist, int& min_dist, bool* visited)
{
    visited[start] = true; // помечаем как посещенную
    if (start == finish){
        min_dist = std::min(dist, min_dist);
    }else
    if (dist < min_dist)        
        for (int i = 0; i < SIZE; i++)
            if (edgeExists(start, i) && !visited[i])
                depthInnerDFS(i, finish, dist + matrix[start][i], min_dist, visited);
   visited[start] = false;             
}
int Graph::findMinWayDFS(int from, int to)
{
    int start = from, finish = to,  min_dist = VERYBIGINT;
    bool visited[SIZE]; // список посещенных вершин
    ///int distances[SIZE];
    for (int i = 0; i < SIZE; i++)
        visited[i] = false; // инициализируем как непосещенные
    depthInnerDFS(start, finish, 0, min_dist, visited);
    return min_dist;
}

@anastasyi · 18.03.2023, 06:14 **[ТС]**

SmallEvil, c количеством вершин в DFS не 0 а 1 тоже не сработало, а вот по весу ребра сработало!Спасибо

@SmallEvil · 18.03.2023, 07:00

Сообщение от anastasyi

а вот по весу ребра сработало!

Но я не вижу в описании ТЗ хоть какого нибудь упоминания о весах ребер, и что они влияют на путь.
Вообщем, из вас там экстрасенсов делают

@anastasyi · 18.03.2023, 08:34 **[ТС]**

SmallEvil, Есть такое)

@Perekhod · 23.05.2023, 15:20

спасибо выше писавшим, сайт принял результат, может кому-нибудь поможет

graph.cpp

C++
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
#include "../headers/graph.h"
#include <iostream>
Graph::Graph() {
    for(int i=0;i < SIZE; i++)
      for(int j=0; j< SIZE; j++)
        matrix[i][j] = 0;
    vertexCount = 0;
}
// добавление вершины
void Graph::addVertex(int vnumber)
{
    vertexes[vertexCount] = vnumber;
    vertexCount++;
}
// добавление ребра
void Graph::addEdge(int v1, int v2, int weight)
{
    matrix[v1][v2] = weight;
    matrix[v2][v1] = weight;
}
// проверка существования ребра
bool Graph::edgeExists(int v1, int v2)
{
    return matrix[v1][v2] > 0;
}
// проверка существования вершины
bool Graph::vertexExists(int v)
{
    for(int i=0;i<vertexCount;i++)
       if(vertexes[i] == v)
          return true;
    return false;
}
 
void Graph::depthInnerDFS(int start, int finish, int dist, int& min_dist, bool* visited)
{
    visited[start] = true;          // помечаем как посещенную
    if (start == finish) 
    {
        min_dist = std::min(dist, min_dist);
    }
    else
        if (dist < min_dist)
            for (int i = 0; i < SIZE; i++)
                if (edgeExists(start, i) && !visited[i])
                    depthInnerDFS(i, finish, dist + matrix[start][i], min_dist, visited);
    visited[start] = false;
}

graph.h

C++
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
#ifndef __GRAPH__
#define __GRAPH__
 
#define SIZE 10
 
class Graph {
    public:
        Graph();
        // добавление вершины
        void addVertex(int vnumber);
        // добавление ребра
        void addEdge(int v1, int v2, int weight);
        // удаление вершины
        void delVertex(int vnumber);
        // удаление ребра
        void delEdge(int v1, int v2);
        //поиск количества путей
        int findMinWayDFS(int v1, int v2);
        
        void inner(
    int current,int to, bool visited[], int& min, int currentDistance);
        
        int dummy1(int v1, int v2);
        void dummy2(void** param);
        void depthInnerDFS(int start, int finish, int dist, int& min_dist, bool* visited);
        
    private:
        bool edgeExists(int v1, int v2);
        bool vertexExists(int v);
 
        int matrix[SIZE][SIZE]; // матрица смежности
         
        int vertexes[SIZE]; // хранилище вершин
        int vertexCount; // количество добавленных вершин
};
#endif

task.h

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include "../headers/graph.h"
// поиск кратчайшего расстояния
#define VERYBIGINT 1000000000
int Graph::findMinWayDFS(int from, int to) 
{
   int start = from, finish = to, min_dist = VERYBIGINT;
    bool visited[SIZE];             // список посещенных вершин
    ///int distances[SIZE];
    for (int i = 0; i < SIZE; i++)
        visited[i] = false;        // инициализируем как непосещенные
    depthInnerDFS(start, finish, 0, min_dist, visited);
    return min_dist;
   return 0;
}

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@anastasyi 1 / 1 / 0 Регистрация: 03.09.2021 Сообщений: 48
	17.03.2023, 15:02 [ТС]
	SmallEvil, попробую додумать, спасибо) Добавлено через 26 минут SmallEvil, Вообще по идее, так и должно быть как у вас, не понимаю, в чем дело 0

@SmallEvil Заблокирован
	17.03.2023, 15:29
	Может тут уже используется вес ребра как "расстояние" между вершинами. ТЗ как будто "не доносили". 0

@anastasyi 1 / 1 / 0 Регистрация: 03.09.2021 Сообщений: 48
	18.03.2023, 06:14 [ТС]
	SmallEvil, c количеством вершин в DFS не 0 а 1 тоже не сработало, а вот по весу ребра сработало!Спасибо 0

@anastasyi 1 / 1 / 0 Регистрация: 03.09.2021 Сообщений: 48
	18.03.2023, 08:34 [ТС]
	SmallEvil, Есть такое) 0

Алгоритм поиска минимального расстояния между двумя вершинами в графе представленном в виде матрицы смежности

Решение