Алгоритм Дейкстра




№ 1/14 Дейкстра: Начало

Read Theory

Дан ориентированный или неориентированный взвешенный граф с n вершинами и m рёбрами. Веса всех рёбер неотрицательны. Указана некоторая стартовая вершина s. Требуется найти длины кратчайших путей из вершины s во все остальные вершины, а также предоставить способ вывода самих кратчайших путей.
 
Эта задача называется "задачей о кратчайших путях с единственным источником" (single-source shortest paths problem).

Выполняет такие же задачи как и 1-K BFS, но без учета K. Также как и 1-K BFS не умеет правильно обрабатывать отрицательные ребра

Алгоритм:
Сам алгоритм Дейкстры состоит из N итераций. На очередной итерации выбирается вершина V  с наименьшим расстоянием до нее из еще не отмеченных вершин, данная вершина становится отмеченной и из нее происходят релаксации соседних вершин.


 итоговая асимптотика алгоритма составляет: O(n2+ m)

Task
Дан ориентированный взвешенный граф. Найдите кратчайшее расстояние от одной заданной вершины до другой.
 
Входные данные
В первой строке содержатся три числа: N, S и F (1≤ N≤ 100, 1≤ S, F≤ N), где N – количество вершин графа, S – начальная вершина, а F – конечная. В следующих N строках вводится по N чисел, не превосходящих 100, – весовая матрица смежности графа, где -1 означает отсутствие ребра между вершинами, а любое неотрицательное число – присутствие ребра данного веса. На главной диагонали матрицы записаны нули.
 
Выходные данные
Требуется вывести искомое расстояние или -1, если пути между указанными вершинами не существует.
 
Ввод Вывод
3 2 1
0 1 1
4 0 1
2 1 0
 3
C++
Write a program below 
#include<iostream>
 
using namespace std;
 
int main()
{
    const int N1 = 110;
    int N, S, F, g[N1][N1], i, j, mini, d[N1];
    bool used[N1];
   
    cin >> N >> S >> F;
   
    fill(used, used + N, false);
   
    fill(d, d + N, 10000000);
   
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
            cin >> g[i][j];
    }
   
    d[S - 1] = 0;
   
    for (i = 0; i < N; i++)
    {
        mini = -1;
       
        for (j = 0; j < N; j++)
        {
            if (!used[j] && (mini == -1 || d[j] < d[mini]))
                mini = j;
        }
       
        used[mini] = true;
       

        
    if (d[F - 1] == 10000000)
        cout << "-1";
    else
        cout << d[F - 1];
}
Your last submission is saved in the editor window.
     

Results:

All results:

©2009 - 2019 SilverTests.ru/en

Education

Quizes
Problems
Courses

My Account

Register
Sign

About us

Contacts
Rules