Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/9: Рейтинг темы: голосов - 9, средняя оценка - 4.67
0 / 0 / 0
Регистрация: 10.03.2019
Сообщений: 16
1

Найти кратчайшее расстояние от одной заданной вершины ориентированного взвешенного графа до другой

08.08.2019, 22:20. Показов 1869. Ответов 1

Алгоритм Дейкстра
Дан ориентированный взвешенный граф. Найдите кратчайшее расстояние от одной заданной вершины до другой.

Входные данные
В первой строке содержатся три числа: N, S и F (1≤ N≤ 100, 1≤ S, F≤ N), где N – количество вершин графа, S – начальная вершина, а F – конечная. В следующих N строках вводится по N чисел, не превосходящих 100, – матрица смежности графа, где -1 означает отсутствие ребра между вершинами, а любое неотрицательное число – присутствие ребра данного веса. На главной диагонали матрицы записаны нули.

Выходные данные
Требуется вывести искомое расстояние или -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
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,s,f;
    cin>>n>>s>>f;
    int a[n+1][n+1]={};
    for(int i=1;i<=n;i++)
        for(int g=1;g<=n;g++)
            cin>>a[i][g];
            
    queue<int>q;    q.push(s);  bool b[n+1]={0};
    int distanse[n+1];  for(int i=1;i<=n;i++)   distanse[i]=101;    distanse[s]=0;
    
    int ans=0,k=0;
    while(!q.empty()){
        int v=q.front();    q.pop();    b[v]=true;
        for(int i=1;i<=n;i++){
            if((a[v][i]>0 && b[i]==false) || (a[v][i]>0 && distanse[i]>distanse[v]+a[v][i])){
                q.push(i);
                if(distanse[i]>distanse[v]+a[v][i]){
                    distanse[i]=distanse[v]+a[v][i];
                }
            }
        }
    }
    if(distanse[f]==101)
        cout<<-1;
    else
        cout<<distanse[f];
}
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.08.2019, 22:20
Ответы с готовыми решениями:

Дан ориентированный взвешенный граф. Найдите кратчайшее расстояние от одной заданной вершины до другой
В первой строке содержатся три числа: N, S и F (1≤N≤100, 1≤S,F≤N), где N — количество вершин графа,...

Найти кратчайшее расстояние из вершины v1 неориентированного взвешенного графа в другие вершины графа
Пользуясь алгоритмом Дейкстры, найти кратчайшее расстояние из вершины v1 неориентированного...

Найти все вершины графа, к которым существует путь заданной длины от выделенной вершины графа
Написать программу на prologuse на русском языке как на примере(Определить, является ли связным...

Найти все пути, соединяющие две вершины ориентированного графа.
Помогите дописать программу. #include&lt;stdio.h&gt; #include&lt;conio.h&gt; int visited; int A; void...

1
0 / 0 / 0
Регистрация: 15.10.2020
Сообщений: 2
25.12.2020, 09:24 2
Alex1603, нашел ошибку?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
25.12.2020, 09:24

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

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

Графы. Найти все вершины заданного графа, недостижимые от заданной его вершины
Найти все вершины заданного графа, недостижимые от заданной его вершины. Помогите решить...

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


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

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

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