Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/3: Рейтинг темы: голосов - 3, средняя оценка - 5.00
Grump
0 / 0 / 0
Регистрация: 13.01.2015
Сообщений: 7
1

Найти длинейший циклический путь в графе

01.02.2015, 20:51. Просмотров 579. Ответов 1
Метки нет (Все метки)

Доброго времени суток, помогите пожалуйста. Я изменил алгоритм Дейкстры, чтобы он выводил мне самый длинный путь от начальной вершины, но мне нужно найти вес длиннейшего циклического пути в графе (т.е. самый длинный путь от первоначального заданной вершины к ней же). Помогите пожалуйста, вот мой код точнее сама функция:

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
void LCW(int start, int M, int **graph)
{
    int distance[N], i, index, u, m = start+1;
    bool visited[N];
    for (i = 0; i < M; i++){
        distance[i] = INT_MIN; 
        visited[i] = false; 
    }
    distance[start] = 0;
    for (int count = 0; count < M-1; count++){
        int max = INT_MIN;              
        for(i = 0; i < M; i++)
            if(!visited[i] && distance[i] >= max){
                max = distance[i];
                index = i;
            }
            u = index;
            visited[u] = true;
            for(i = 0; i < M; i++)
                if(!visited[i] && graph[u][i] && distance[u] != INT_MIN && 
                    distance[u] + graph[u][i] > distance[i])
                    distance[i] = distance[u] + graph[u][i];
    }
    int from, to, MaxEl = distance[0];
    for (i = 0; i < M; i++)
        if(distance[i] != INT_MIN && distance[i] > MaxEl){
            MaxEl = distance[i];
            from = m;
            to = i;
        }
        printf("Самый длинный по весу путь от вершины %d до %d его вес %d\n", from, to+1, MaxEl);
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.02.2015, 20:51
Ответы с готовыми решениями:

Найти путь в графе
подскажите какой алгоритм поиска лучше применить и как в данной задаче &quot; В системе двусторонних...

Нужно найти максимальный простой путь в графе
Здравствуйте Есть такая задача: &quot;Нужно найти максимальный простой путь в графе&quot; Как я понял,...

Найти наибольший циклический путь в графе
Есть граф Ввод: 0 1 0 0 1 0 1 0 1 1 0 0 Вывод 5

Циклический путь в графе
Задача стоит так: &quot;определить самый длинный (по весу) циклический путь в этом графе&quot; граф...

Длинейший путь графа
Здраствуйте, помогите пожалуйста. Нужно найти самый длиный простой путь в графе. Написал...

1
Grump
0 / 0 / 0
Регистрация: 13.01.2015
Сообщений: 7
03.02.2015, 12:27  [ТС] 2
подскажите пожалуйста
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.02.2015, 12:27

Найти путь в графе
max_versh = 10; matr = zeros(max_versh,max_versh); opt_versh = 7; matr (1,2) = 1; matr (2,6)...

Найти путь в ориентированном графе
Здравствуйте, помогите, пожалуйста, решить задачу: Дан список взвешенных дуг ориентированного...

Найти максимальный путь в графе
Аллаху акбар, парни. есть задача, необходимо построить такой многоугольник(не обязательно выпуклый)...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru