Module: Dijkstra-Algorithmus


Problem

1/14

Dijkstra: Anfang (C++)

Theory Click to read/hide

Dun ist eine orientierte oder unorientierte gewichtete Zählung mit n Tops und m Rippen. Die Gewichte aller Rippen sind faszinierend. Einige Ausgangspunkte s. Es besteht die Notwendigkeit, die Länge der kürzesten Pfade von der Oberseite von s zu allen anderen Gipfeln zu finden, und einen Weg, die kürzesten Pfade selbst zu bringen.
Es heißt "single-source kürzeste Pfade Problem."

Ergänzt die gleichen Aufgaben wie 1-K BFS, aber nicht K. Auch kann 1-K BFS negative Rippen richtig handhaben

Algorithmen:
Der Dayxtra-Algorithmus selbst besteht aus N terations. Bei einer anderen Iteration ist der Peak V mit dem tiefsten Abstand zu ihm von den unmarkierten Spitzen zu wählen, der Peak zu markieren und die Reklamation der benachbarten Gipfel zu erfolgen.


Der Gesamtalgorithmus asymptomy ist: O(n)2+ m)

Problem

Es wurde ein orientiertes gewichtetes Diagramm angegeben. Finden Sie den kürzesten Abstand von einem bestimmten Scheitelpunkt zum anderen.
 
Eingabe
Die erste Zeile enthält drei Zahlen: N, S und F (1≤ N≤ 100, 1≤ S, F≤ N), wobei N – die Anzahl der Eckpunkte des Graphen, S – der Anfangsscheitelpunkt und F – der Endpunkt ist. Die folgenden N Zeilen werden mit N Zahlen eingegeben, die nicht größer als 100 sind, – die Gewichtungsmatrix für die Adjazenz des Graphen, wobei -1 bedeutet, dass keine Kante zwischen den Eckpunkten fehlt und jede nicht negative Zahl die Anwesenheit einer Kante dieses Gewichts ist. Auf der Hauptdiagonale der Matrix sind Nullen geschrieben.
 
Ausgabe
Sie möchten den gewünschten Abstand oder -1 anzeigen, wenn kein Pfad zwischen den angegebenen Scheitelpunkten vorhanden ist.

Beispiele
№ Eingabe Ausgabe
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!