Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.64/11: Рейтинг темы: голосов - 11, средняя оценка - 4.64
ARTER616
1 / 1 / 3
Регистрация: 14.01.2017
Сообщений: 283
1

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

02.02.2018, 21:32. Просмотров 1919. Ответов 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <cstring>
using namespace std;
const int inf = 1000000000;
int n = 2;
int D[n];
int color[n];
void init(int v) {
  for (int i = 0; i < n; ++i) {
    D[i] = inf;
    color[i] = 0;
    }
    D[v] = 0; 
    color[v] = 1; 
}
void relax(int x) {
  for (int i = 0; i < n; ++i)
  if (D[i] > D[x] + A[x][i])
  D[i] = D[x] + A[x][i];
}
int findMin() {
  int x = -1;
  int dist = inf;
  for (int i = 0; i < n; ++i) {
    if (D[i] < dist && color[i] == 0) {
      x = i;dist = D[i]; 
    }
  }
  return x;
}
void Dijkstra(int v) {
  init(v);
  relax(v);
  for (int x = findMin(); x != -1; x = findMin()){
    color[x] = 1;
    relax(x);
  }
}
int main(){
  int N, S, F;
  cin >> N, S, F;
  int arr[N][N];
  for(int i =0; i<N; i++){
  for(int j =0; j<N; j++){
    cin>>arr[i][j];
  }
  }
  
  Dijkstra(N);
  
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.02.2018, 21:32
Ответы с готовыми решениями:

Дан ориентированный граф найти, возможно ли попасть из вершины К в вершину M
Дан ориентированный граф найти, возможно ли попасть из вершины К в вершину M ...

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

Определить кратчайшее расстояние от заданной точки до границы заданной фигуры
Определить кратчайшее расстояние от заданной точки до границы заданной фигуры, если точка находится...

Определить кратчайшее расстояние от заданной точки до границы заданной фигуры, считая, что точка находится вне
Определить кратчайшее расстояние от заданной точки до границы заданной фигуры, считая, что точка...

Дан ориентированный граф. Найти все сильно связные компоненты графа
Есть вот такой код, очень прошу исправить под задание в теме поста Спасибо заранее! #include...

1
igorrr37
2033 / 1599 / 798
Регистрация: 21.12.2010
Сообщений: 2,751
Записей в блоге: 10
03.02.2018, 15:58 2
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include <cstring>
#include <fstream>
#include <cstdlib>
#include <climits>
#include <algorithm>
#include <iomanip>
using namespace std;
 
int findMin(int* weight, bool* mark, int n) 
{
    int ind = -1;
    int minWeight = INT_MAX;
    for (int i = 0; i < n; ++i) 
    {
        if (weight[i] <= minWeight && mark[i] == false)
        {
            ind = i; 
            minWeight = weight[i];
        }
    }
    return ind;
}
 
int main() 
{
    std::ifstream ifs("in.txt");
    if (!ifs.is_open())
    {
        std::cerr << "Unable to open file\n";
        exit(1);
    }
    int n, s, f;
    ifs >> n >> s >> f;
    std::cout << n << ' ' << s << ' ' << f << std::endl;
    --s;
    --f;
    int** mtx = new int*[n];
    for (int i = 0; i < n; ++i) 
    {
        mtx[i] = new int[n];
        for (int j = 0; j < n; ++j)
        {
            ifs >> mtx[i][j];
            std::cout << std::setw(4) << mtx[i][j];
        }
        std::cout << std::endl;
    }
 
    // Dijkstra
    bool* mark = new bool[n];
    int* weight = new int[n];
    for (int i = 0; i < n; ++i)
    {
        mark[i] = false;
        weight[i] = INT_MAX;
    }
 
 
    int cur = s;
    weight[cur] = 0;
    mark[cur] = true;
    
    while (true)
    {
        for (int j = 0; j < n; ++j)
        {
            if (mtx[cur][j] > 0 && false == mark[j])
            {
                int weightJ = mtx[cur][j] + weight[cur];
                if (weightJ < weight[j])
                {
                    weight[j] = weightJ;
                }
            }
        }
 
        cur = findMin(weight, mark, n);
 
        if (cur == -1)
        {
            break; // path doesnt exist, quit
        }
        else
        {
            mark[cur] = true;
            if (cur == f)
            {
                break; // path found, quit
            }
        }
    }
    if (cur == f && weight[cur] != INT_MAX)
    {
        std::cout << "dist: " << weight[cur] << std::endl;
    }
    else
    {
        std::cout << -1 << std::endl;
    }
 
 
 
    for (int i = 0; i < n; i++)
    {
        delete[] mtx[i];
    }
    delete[] mtx;
    delete[] mark;
    delete[] weight;
    ifs.close();
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.02.2018, 15:58

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

В заданном графе найдите все вершины, растояние от которых до заданной вершины равно 2
гласит так: &quot;В заданном графе найдите все вершины, растояние от которых до заданной вершины равно...

Как преобразовать неориентированный граф в ориентированный граф из матричной записи
Есть ли какой нибудь алгоритм преобразования Неориентированный графа в ориентированный граф из...


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

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

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