Module: Algoritmo di Dijkstra


Problem

1/14

Dijkstra: L'inizio (C++)

Theory Click to read/hide

Dato un grafo pesato orientato o non orientato con n vertici e m archi. I pesi di tutti i bordi sono non negativi. Alcuni vertici iniziali s sono specificati. Devi trovare le lunghezze dei percorsi più brevi dal vertice s a tutti gli altri vertici e fornire anche un modo per stampare i percorsi più brevi stessi.
 
Questo problema è chiamato "problema del percorso più breve a origine singola" (problema dei cammini minimi a sorgente singola).

Esegue le stesse attività di 1-K BFS, ma senza tener conto di K. Inoltre, come 1-K BFS, non gestisce correttamente i fronti negativi

Algoritmo:
L'algoritmo di Dijkstra stesso consiste di N iterazioni. Alla successiva iterazione, il vertice V  con la minima distanza da esso tra i vertici non ancora marcati, questo vertice diventa marcato e da esso si verificano rilassamenti dei vertici vicini.


 il comportamento asintotico finale dell'algoritmo è: O(n2+ m)

Problem

Ti viene fornito un grafico ponderato diretto. Trova la distanza più breve da un dato vertice a un altro.
 
Input
La prima riga contiene tre numeri: N, S e F (1≤ N≤ 100, 1≤ S, F≤ N), dove N – numero di vertici del grafico, S – vertice iniziale e F – finale. Nelle successive N righe, inserisci N numeri ciascuno, non superiore a 100, – matrice di adiacenza del peso del grafico, dove -1 significa nessun bordo tra i vertici e qualsiasi numero non negativo – la presenza di un bordo di peso dato. Gli zeri sono scritti sulla diagonale principale della matrice.
 
Uscita
È necessario visualizzare la distanza desiderata o -1 se non esiste un percorso tra i vertici specificati.

Esempi
# Input Uscita
1
3 2 1
0 1 1
4 0 1
2 1 0
 3

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the 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];
}

     

Program check result

To check the solution of the problem, you need to register or log in!