Module: Algorithme de Dijkstra


Problem

1/14

Dijkstra : le début (C++)

Theory Click to read/hide

Étant donné un graphe pondéré orienté ou non orienté avec n sommets et m arêtes. Les poids de toutes les arêtes sont non négatifs. Un sommet de départ s est spécifié. Vous devez trouver les longueurs des chemins les plus courts du sommet s à tous les autres sommets, et également fournir un moyen d'imprimer les chemins les plus courts eux-mêmes.
 
Ce problème est appelé "problème du chemin le plus court à source unique" (problème des chemins les plus courts à source unique).

Effectue les mêmes tâches que 1-K BFS, mais sans tenir compte de K. De plus, comme 1-K BFS, il ne gère pas correctement les fronts négatifs

Algorithme :
L'algorithme de Dijkstra lui-même se compose de N itérations. A l'itération suivante, le sommet V  avec la plus petite distance à lui parmi les sommets non encore marqués, ce sommet devient marqué et les relaxations des sommets voisins se produisent à partir de lui.


 le comportement asymptotique final de l'algorithme est : O(n2+ m)

Problem

On vous donne un graphique pondéré orienté. Trouver la distance la plus courte entre un sommet donné et un autre.
 
Entrée
La première ligne contient trois nombres : N, S et F (1≤ N≤ 100, 1≤ S, F≤ N), où N – nombre de sommets du graphe, S – sommet initial, et F – final. Dans les N lignes suivantes, entrez N nombres chacun, n'excédant pas 100, – pondérer la matrice d'adjacence du graphe, où -1 signifie qu'il n'y a pas d'arête entre les sommets, et tout nombre non négatif – la présence d'une arête de poids donné. Des zéros sont écrits sur la diagonale principale de la matrice.
 
Sortie
Il est nécessaire d'afficher la distance souhaitée ou -1 s'il n'y a pas de chemin entre les sommets spécifiés.

Exemples
3 2 1
0 1 1
4 0 1
2 1 0
# Entrée Sortie
1 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!