Schauen wir uns das Beispiel der Suche nach dem kürzesten Weg an. Ein Netz von Autobahnen, die die Regionen der Stadt verbinden, ist vorhanden. Manche Straßen sind Einbahnstraßen. Finden Sie die kürzesten Routen vom Stadtzentrum zu jeder Stadt in der Region.
Um dieses Problem zu lösen, können Sie verwenden Dijkstras Algorithmus ist ein Graphalgorithmus, der 1959 vom niederländischen Wissenschaftler E. Dijkstra erfunden wurde. Ermittelt den kürzesten Abstand von einem der Eckpunkte des Diagramms zu allen anderen. Funktioniert nur für Diagramme ohne negative Gewichtskanten.
Angenommen, Sie müssen die kürzesten Abstände vom ersten Scheitelpunkt zu allen anderen finden.
Die Kreise geben die Eckpunkte an, die Linien die Pfade zwischen ihnen (die Kanten des Diagramms). In den Kreisen sind die Nummern der Scheitelpunkte angegeben, über den Kanten ist ihr Gewicht angegeben – die Länge des Weges. Neben jedem Scheitelpunkt befindet sich eine rote Markierung – die Länge des kürzesten Weges zu diesem Scheitelpunkt von Scheitelpunkt 1.
Die Beschriftung von Scheitelpunkt 1 selbst wird auf 0 gesetzt, die Beschriftungen anderer Scheitelpunkte werden auf eine unerreichbar große Zahl (idealerweise unendlich) gesetzt. Dies spiegelt wider, dass die Abstände von Scheitelpunkt 1 zu anderen Scheitelpunkten noch nicht bekannt sind. Alle Eckpunkte des Diagramms werden als nicht besucht markiert. 
Erster Schritt
Scheitelpunkt 1 hat die minimale Bezeichnung. Seine Nachbarn sind die Scheitelpunkte 2, 3 und 6. Wir gehen der Reihe nach um die Nachbarn des Scheitelpunkts herum.
Der erste Nachbar von Scheitelpunkt 1 ist Scheitelpunkt 2, da die Länge des Pfads dorthin minimal ist. Die Länge des Weges dorthin durch Scheitelpunkt 1 ist gleich der Summe aus der kürzesten Entfernung zu Scheitelpunkt 1, dem Wert seiner Beschriftung und der Länge der Kante, die vom 1. zum 2. verläuft, also 0 + 7 = 7. Dies ist kleiner als die aktuelle Bezeichnung von Scheitelpunkt 2 (10000), sodass die neue Bezeichnung des zweiten Scheitelpunkts 7 ist. 
Ebenso ermitteln wir die Pfadlängen für alle anderen Nachbarn (Eckpunkte 3 und 6).
Alle Nachbarn von Scheitelpunkt 1 werden überprüft. Der aktuelle Mindestabstand zum Gipfel 1 gilt als endgültig und kann nicht geändert werden. Scheitelpunkt 1 ist als besucht markiert.
Zweiter Schritt
Schritt 1 des Algorithmus wird wiederholt. Wieder finden wir den „nächsten“ der nicht besuchten Eckpunkte. Dies ist Scheitelpunkt 2 mit der Bezeichnung 7.
Wieder versuchen wir, die Beschriftungen der Nachbarn des ausgewählten Scheitelpunkts zu reduzieren, indem wir versuchen, durch den 2. Scheitelpunkt in sie hineinzugehen. Die Nachbarn von Scheitelpunkt 2 sind die Scheitelpunkte 1, 3 und 4.
Scheitelpunkt 1 wurde bereits besucht. Der nächste Nachbar von Scheitelpunkt 2 ist Scheitelpunkt 3, da er die minimale Beschriftung der als nicht besucht markierten Scheitelpunkte hat. Wenn Sie über 2 dorthin gehen, beträgt die Länge eines solchen Pfads 17 (7 + 10 = 17). Aber die aktuelle Bezeichnung des dritten Scheitelpunkts ist 9 und 9< 17, поэтому метка не меняется.
Ein weiterer Nachbar von Scheitelpunkt 2 ist Scheitelpunkt 4. Wenn Sie ihn über den 2. Punkt erreichen, beträgt die Länge eines solchen Pfads 22 (7 + 15 = 22). Seit dem 22<10000, устанавливаем метку вершины 4 равной 22.
Alle Nachbarn von Scheitelpunkt 2 wurden angezeigt. Markieren Sie ihn als besucht.
Dritter Schritt
Wir wiederholen den Algorithmusschritt und wählen den Scheitelpunkt 3 aus. Nach der „Verarbeitung“ erhalten wir die folgenden Ergebnisse. 
Vierter Schritt
Fünfter Schritt
Sechster Schritt
Somit ist der kürzeste Weg von Scheitelpunkt 1 zu Scheitelpunkt 5 der Weg durch die Scheitelpunkte 1 — 3 — 6 — 5
, da wir auf diese Weise ein Mindestgewicht von 20 erreichen.
Beginnen wir mit der Ableitung des kürzesten Weges. Wir kennen die Pfadlänge für jeden Scheitelpunkt und betrachten nun die Scheitelpunkte vom Ende aus. Wir betrachten den letzten Scheitelpunkt (in diesem Fall den Scheitelpunkt). 5
) und für alle Eckpunkte, mit denen es verbunden ist, ermitteln wir die Pfadlänge, indem wir das Gewicht der entsprechenden Kante von der Pfadlänge des endgültigen Eckpunkts subtrahieren.
Ja, die Spitze 5
hat Pfadlänge 20
. Es ist mit den Gipfeln verbunden 6
Und 4
.
Für die Spitze 6
Wir bekommen das Gewicht 20 - 9 = 11 (übereinstimmend).
Für die Spitze 4
Wir bekommen das Gewicht 20 - 6 = 14 (stimmte nicht überein).
Wenn wir als Ergebnis einen Wert erhalten, der mit der Pfadlänge des betreffenden Scheitelpunkts (in diesem Fall des Scheitelpunkts) übereinstimmt 6
), dann erfolgte von dort aus der Übergang zum endgültigen Scheitelpunkt. Wir markieren diesen Gipfel auf dem gewünschten Weg.
Als nächstes bestimmen wir die Kante, durch die wir zum Scheitelpunkt gelangt sind 6
. Und so weiter, bis wir am Anfang angelangt sind.
Wenn wir als Ergebnis einer solchen Durchquerung irgendwann die gleichen Werte für mehrere Scheitelpunkte haben, können wir jeden davon nehmen – mehrere Pfade haben die gleiche Länge.
Implementierung des Dijkstra-Algorithmus
Zur Speicherung der Gewichte des Diagramms wird eine quadratische Matrix verwendet. Die Zeilen- und Spaltenüberschriften enthalten die Eckpunkte des Diagramms. Und die Gewichte der Diagrammbögen werden in den internen Zellen der Tabelle platziert. Der Graph enthält keine Schleifen, daher enthält die Hauptdiagonale der Matrix Nullwerte.
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | 0 | 7 | 9 | 0 | 0 | 14 |
| 2 | 7 | 0 | 10 | 15 | 0 | 0 |
| 3 | 9 | 10 | 0 | 11 | 0 | 2 |
| 4 | 0 | 15 | 11 | 0 | 6 | 0 |
| 5 | 0 | 0 | 0 | 6 | 0 | 9 |
| 6 | 14 | 0 | 2 | 0 | 9 | 0 |
Implementierung in 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
#define _CRT_SECURE_NO_WARNINGS
#enthalten
#enthalten
#define GRÖSSE 6
int main()
{
int a; // Verbindungsmatrix
int d; // Mindestabstand
im Fernsehen; // besuchte Eckpunkte
int temp, minindex, min;
int begin_index = 0;
system("chcp 1251" );
system("cls" );
// Initialisiere die Verbindungsmatrix
für (int i = 0; i
a[i][i] = 0;
für (int j = i + 1; j
scanf("%d" , &temp);
a[i][j] = temp;
a[j][i] = temp;
}
}
// Verbindungsmatrix ausgeben
für (int i = 0; i
für (int j = 0; j
printf("\n" );
}
//Initialisierung von Scheitelpunkten und Abständen
für (int i = 0; i
d[i] = 10000;
v[i] = 1;
}
d = 0;
// Algorithmusschritt
Tun (
Mindestindex = 10000;
min = 10000;
für (int i = 0; i
if ((v[i] == 1) && (d[i]
min = d[i];
minindex = i;
}
}
// Das gefundene Mindestgewicht hinzufügen
// zum aktuellen Gewicht des Scheitelpunkts
// und mit dem aktuellen Mindestgewicht des Scheitelpunkts vergleichen
if (minindex != 10000)
{
für (int i = 0; i
wenn (a[i] > 0)
{
temp = min + a[i];
wenn (temp< d[i])
{
d[i] = temp;
}
}
}
v = 0;
}
) while (minindex< 10000);
// Kürzeste Abstände zu Scheitelpunkten ausgeben
printf( „\nKürzeste Abstände zu den Eckpunkten:\n“);
für (int i = 0; i
// Pfad wiederherstellen
int ver; // Array der besuchten Eckpunkte
int end = 4; // Endscheitelpunktindex = 5 - 1
ver = Ende + 1; // Startelement – Endscheitelpunkt
int k = 1; // Index des vorherigen Scheitelpunkts
int Gewicht = d; // Gewicht des letzten Scheitelpunkts
while (end != begin_index) // bis wir den Anfangsscheitelpunkt erreichen
{
für (int i = 0; i
if (a[i] != 0) // wenn eine Verbindung besteht
{
int temp = Gewicht - a[i]; // Bestimmen Sie das Gewicht des Pfads vom vorherigen Scheitelpunkt
if (temp == d[i]) // wenn das Gewicht mit dem berechneten übereinstimmt
{ // das bedeutet, dass es einen Übergang von diesem Scheitelpunkt gab
Gewicht = Temperatur; // das neue Gewicht speichern
Ende = i; // den vorherigen Scheitelpunkt speichern
ver[k] = i + 1; // und schreibe es in ein Array
k++;
}
}
}
// Den Pfad ausgeben (der Startscheitelpunkt landete am Ende des Arrays aus k Elementen)
printf( „\nGeben Sie den kürzesten Weg aus\n“);
for (int i = k - 1; i >= 0; i--)
printf("%3d", ver[i]);
getchar(); getchar();
0 zurückgeben;
}
Ausführungsergebnis
Zurück: kürzester Weg ist heute eine lebenswichtige Aufgabe und wird fast überall eingesetzt, von der Suche nach der optimalen Route zwischen zwei Objekten am Boden (z. B. dem kürzesten Weg von zu Hause zur Universität), in Autopilot-Systemen bis hin zur Suche nach der optimalen Route beim Transport und dem Austausch von Informationspaketen in Netzwerken usw.
Der kürzeste Weg wird mithilfe eines mathematischen Objekts namens Graph betrachtet. Suchen kürzester Weg wird zwischen zwei gegebenen Eckpunkten im Diagramm durchgeführt. Das Ergebnis ist ein Pfad, also eine Folge von Scheitelpunkten und Kanten, die auf zwei benachbarte Scheitelpunkte fallen, und seine Länge.
Schauen wir uns drei der meisten an effizienter Algorithmus finden kürzester Weg:
- Dijkstras Algorithmus;
- Floyds Algorithmus;
- Suchalgorithmen.
Diese Algorithmen lassen sich leicht mit einer kleinen Anzahl von Eckpunkten im Diagramm ausführen. Mit zunehmender Zahl nimmt das Suchproblem zu kürzester Weg wird komplizierter.
Dijkstras Algorithmus
Bei diesem Algorithmus handelt es sich um einen Graphalgorithmus, der 1959 vom niederländischen Wissenschaftler E. Dijkstra erfunden wurde. Der Algorithmus ermittelt den kürzesten Abstand von einem der Eckpunkte des Diagramms zu allen anderen und funktioniert nur für Diagramme ohne Kanten mit negativem Gewicht.
Jedem Scheitelpunkt wird eine Gewichtung zugewiesen – dies ist die Gewichtung des Pfades vom ursprünglichen Scheitelpunkt bis zu diesem. Außerdem kann jeder Scheitelpunkt ausgewählt werden. Wenn ein Scheitelpunkt ausgewählt ist, ist der Weg von ihm zum ursprünglichen Scheitelpunkt der kürzeste. Wenn nicht, ist er temporär. Beim Durchlaufen des Diagramms berechnet der Algorithmus die Route für jeden Scheitelpunkt und wählt den Scheitelpunkt aus, wenn er sich als der kürzeste herausstellt. Das Gewicht dieses Scheitelpunkts wird zum Gewicht des Pfades. Für alle Nachbarn eines bestimmten Scheitelpunkts berechnet der Algorithmus auch das Gewicht, wählt sie jedoch keinesfalls aus. Der Algorithmus beendet seine Arbeit, nachdem er den endgültigen Scheitelpunkt und das Gewicht erreicht hat kürzester Weg wird zum Gewicht des letzten Scheitelpunkts.
Dijkstras Algorithmus
Schritt 1. Allen Scheitelpunkten außer dem ersten wird eine Gewichtung gleich unendlich zugewiesen, und dem ersten Scheitelpunkt wird eine Gewichtung gleich 0 zugewiesen.
Schritt 2. Es sind nicht alle Scheitelpunkte ausgewählt.
Schritt 3. Der erste Scheitelpunkt wird als aktuell deklariert.
Schritt 4. Das Gewicht aller nicht ausgewählten Scheitelpunkte wird mithilfe der Formel neu berechnet: Das Gewicht eines nicht ausgewählten Scheitelpunkts ist die Mindestzahl des alten Gewichts dieses Scheitelpunkts, der Summe des Gewichts des aktuellen Scheitelpunkts und des Gewichts der Kante, die ihn verbindet aktuellen Scheitelpunkt zum nicht ausgewählten Scheitelpunkt.
Schritt 5. Unter den nicht ausgewählten Scheitelpunkten wird der Scheitelpunkt mit dem minimalen Gewicht gesucht. Wenn keiner gefunden wird, d. h. das Gewicht aller Scheitelpunkte gleich unendlich ist, existiert die Route nicht. Daher ist die Ausgabe . Andernfalls wird der gefundene Scheitelpunkt zum aktuellen. Sie fällt auf.
Schritt 6. Wenn der aktuelle Scheitelpunkt der letzte ist, wird der Pfad gefunden und sein Gewicht ist das Gewicht des letzten Scheitelpunkts.
Schritt 7. Gehen Sie zu Schritt 4.
Bei der Softwareimplementierung Dijkstras Algorithmus Konstruieren wir eine Menge S von Eckpunkten, für die die kürzesten Wege vom Ausgangsscheitelpunkt bereits bekannt sind. Bei jedem Schritt wird einer der verbleibenden Scheitelpunkte zur Menge S hinzugefügt, dessen Abstand vom ursprünglichen Scheitelpunkt geringer ist als für die anderen verbleibenden Scheitelpunkte. In diesem Fall verwenden wir das Array D, in das die Längen geschrieben werden kürzeste Wege für jeden Scheitelpunkt. Wenn die Menge S alle Eckpunkte des Graphen enthält, enthält das Array D die Längen kürzeste Wege vom Startscheitelpunkt zu jedem Scheitelpunkt.
Zusätzlich zu den angegebenen Arrays verwenden wir eine Matrix der Längen C, wobei Element C die Länge der Kante (i,j) ist. Wenn keine Kante vorhanden ist, wird angenommen, dass ihre Länge gleich unendlich ist, d. h , größer als jede tatsächliche Länge der Kanten. Tatsächlich ist die Matrix C Adjazenzmatrix, in dem alle Nullelemente durch Unendlich ersetzt werden.
Um das festzustellen
Der Dijkstra-Algorithmus ist ein Graphalgorithmus, der den kürzesten Weg zwischen zwei gegebenen Eckpunkten in einem Graphen mit nicht negativen Bogenlängen findet. Oft wird auch die Aufgabe gestellt, den kürzesten Weg von einem gegebenen Scheitelpunkt zu allen anderen zu berechnen. Der Algorithmus wird häufig in der Programmierung verwendet, beispielsweise in Routing-Protokollen.
Beschreibung
Die Eingabe des Algorithmus ist ein gewichteter gerichteter Graph mit Bögen mit nicht negativem Gewicht. Die Ausgabe ist eine Reihe kürzester Pfade von einem bestimmten Scheitelpunkt zu anderen.
Zu Beginn wird davon ausgegangen, dass der Abstand für den Anfangsscheitelpunkt Null ist und die Abstände zu allen anderen als unendlich angenommen werden. Ein Array von Flags, die angeben, ob der Scheitelpunkt übergeben wurde, ist mit Nullen gefüllt. Dann wird bei jedem Schritt des Zyklus ein Scheitelpunkt mit einem Mindestabstand zum Original und einem Flag gleich Null gesucht. Dafür wird ein Flag gesetzt und alle benachbarten Eckpunkte überprüft. Wenn der zuvor berechnete Abstand vom ursprünglichen Scheitelpunkt zum überprüften Scheitelpunkt größer ist als die Summe aus dem Abstand zum aktuellen Scheitelpunkt und der Länge der Kante von diesem zum überprüften Scheitelpunkt, wird der Abstand zum überprüften Scheitelpunkt gleichgesetzt zum Abstand zum aktuellen + Kante vom aktuellen zum überprüften. Der Zyklus endet, wenn die Flags aller Scheitelpunkte gleich 1 werden oder wenn der Abstand zu allen Scheitelpunkten mit einem Flag von 0 unendlich ist. Der letzte Fall ist genau dann möglich, wenn der Graph nicht zusammenhängend ist.
Dijkstras Algorithmus im Pseudocode
Eingang: MIT: Array von reellen – Matrix der Bogenlängen des Graphen; s ist der Scheitelpunkt, von dem aus der kürzeste Weg gesucht wird, und t ist der Scheitelpunkt, zu dem er gesucht wird.
Ausgabe: Vektoren T: Array von reellen; und N: Array von 0..r. Wenn die Spitze v liegt auf dem kürzesten Weg von S Zu T, Das Fernseher]- Länge des kürzesten Weges von S Zu y; Also] - der Höhepunkt unmittelbar davor bei auf dem kürzesten Weg.
Н – ein Array, in dem Scheitelpunkt n dem Scheitelpunkt m entspricht, dem vorherigen auf dem Weg von s nach n.
T ist ein Array, in dem Scheitelpunkt n dem Abstand von ihm zu s entspricht.
X ist ein Array, in dem Scheitelpunkt n 1 entspricht, wenn der Pfad dorthin bekannt ist, und 0, wenn nicht.
Array-Initialisierung:
für v von 1 bis R Tun
T[v]: = ∞ (kürzester Weg unbekannt)
X[v]: = 0 (alle Eckpunkte sind unmarkiert)
H[s]: = 0 ( S nichts geht voraus)
T[s]: = 0 (kürzester Weg hat Länge 0...)
X[s]: = 1 (...und er ist berühmt) v : = S (aktuell oben)
M: (Aktualisierungshinweise)
für und ∈ G( Und) Tun
Wenn X[i] = 0 & T[i]> Fernseher] + C Dann
T[i]: = Fernseher] + C(habe eine kürzere Route von gefunden S V Und durch v }
H[u]:= v(erinnere dich dran)
M: = ∞
v : = 0
(Das Ende des kürzesten Weges finden)
für Und von 1 bis P Tun
Wenn X[u] = 0 &T[u]< T Dann
v:= u;
M:= T[u](Spitze v endet auf dem kürzesten Weg S
Wenn v = 0 dann
stoppen (kein Weg von S V T) end if
Wenn v= T Dann
stop ( hat den kürzesten Weg von gefunden S V T) end if
X[v]: = 1 ( den kürzesten Weg gefunden von S V v ) gehe zu M
Begründung
Um die Korrektheit des Dijkstra-Algorithmus zu beweisen, reicht es zu beachten, dass jedes Mal, wenn der Schleifenkörper, der mit der Bezeichnung M beginnt, ausgeführt wird, v Es wird ein Scheitelpunkt verwendet, für den der kürzeste Weg vom Scheitelpunkt bekannt ist S. Mit anderen Worten, wenn X[v] = 1, dann ist T[v] = d(s,v) , und alle Eckpunkte auf dem durch den Vektor H definierten Pfad (s,v) haben die gleiche Eigenschaft, d. h
Vu T[u] = 1 => T[u] = d(s,u)&T] = 1.
Tatsächlich (durch Induktion) das erste Mal als v Es wird ein Scheitelpunkt s verwendet, für den der kürzeste Pfad leer ist und die Länge 0 hat (nicht leere Pfade können nicht kürzer sein, da die Längen der Bögen nicht negativ sind). Sei T[u] = d(s,u) für alle zuvor markierten Eckpunkte Und. Betrachten Sie den neu beschrifteten Scheitelpunkt v, der aus der Bedingung T[v] = min T[i] ausgewählt wird. Beachten Sie, dass, wenn der Pfad bekannt ist, der durch die markierten Eckpunkte verläuft, auch der kürzeste Pfad bekannt ist. Nehmen wir (durch Widerspruch) an, dass T[v] > d(s, v), also der gefundene Weg, der von aus führt S V v, ist nicht die kürzeste. Dann muss es auf diesem Pfad unmarkierte Eckpunkte geben. Betrachten Sie den ersten Scheitelpunkt w auf diesem Weg, so dass T[w] = 0.Wir haben: T[w] = d(s,w)⩽d(s>v)< Т[v],что противоречит выбору вершины u.
Zeitkomplexität
Die Komplexität des Dijkstra-Algorithmus hängt von der Methode zum Finden eines nicht besuchten Scheitelpunkts mit dem Mindestabstand zum ursprünglichen Scheitelpunkt, der Methode zum Speichern der Menge der nicht besuchten Scheitelpunkte und der Methode zum Aktualisieren von Beschriftungen ab. Sei n die Anzahl der Eckpunkte und m die Anzahl der Kanten im Diagramm. Wenn dann im einfachsten Fall nach einem Scheitelpunkt mit dem minimalen Abstand zum ursprünglichen Scheitelpunkt gesucht wird, wird der gesamte Satz von Scheitelpunkten gescannt und ein Array zum Speichern der Abstände verwendet. Die Laufzeit des Algorithmus beträgt O(n 2 ). Die Hauptschleife wird etwa n-mal ausgeführt, wobei in jeder Schleife etwa n Operationen zur Ermittlung des Minimums aufgewendet werden. Zyklen durch die Nachbarn jedes besuchten Scheitelpunkts erfordern eine Anzahl von Operationen proportional zur Anzahl der Kanten m (da jede Kante in diesen Zyklen genau zweimal vorkommt und eine konstante Anzahl von Operationen erfordert). Somit beträgt die Gesamtlaufzeit des Algorithmus O(n 2 +m), aber da m viel kleiner als n(n-1) ist, ist das Endergebnis O(n 2).
Für spärliche Diagramme (d. h. solche, bei denen m viel kleiner als n² ist) können nicht besuchte Scheitelpunkte im binären Heap gespeichert und Abstandswerte als Schlüssel verwendet werden. Da die Schleife etwa n-mal ausgeführt wird und die Anzahl der Relaxationen (Labelwechsel) nicht mehr als m beträgt, beträgt die Laufzeit einer solchen Implementierung O(nlogn+mlogn)
Beispiel
Berechnung der Entfernungen von Scheitelpunkt 1 basierend auf überfahrbaren Scheitelpunkten:
In jede Stadt der Region (sofern Sie sich nur auf Straßen fortbewegen können).
Option 2. Es gibt eine Reihe von Flügen zwischen Städten auf der Welt, deren Kosten jeweils bekannt sind. Die Kosten für einen Flug von A nach B entsprechen möglicherweise nicht den Kosten für einen Flug von B nach A. Finden Sie die kostengünstigste Route (möglicherweise mit Transfers) von Kopenhagen nach Barnaul.
Formale Definition
Beispiel
Betrachten wir die Ausführung des Algorithmus am Beispiel des in der Abbildung gezeigten Diagramms.
Angenommen, Sie müssen die kürzesten Abstände vom ersten Scheitelpunkt zu allen anderen finden.
Implementierungen in Programmiersprachen
Ausführung in der Sprache C (C).
#define SIZE 6 #define INF 1000000000 int a [ SIZE ][ SIZE ] = (( INF , 5 , INF , INF , INF , INF ),( 1 , 2 , 3 , 4 , 5 , 6 ), // Pfadmatrix (1, 2, 3, 4, 5, 6),(1, 2, 3, 4, 5, 6), // horizontale Indizes vom Punkt { 1 , 2 , 3 , 4 , 5 , 6 },{ 1 , 2 , 3 , 4 , 5 , 6 }}; // vertikal zu einem Punkt, Wert - Gewicht int d[GRÖSSE]; // Array der gefundenen kürzesten Pfade, Indizes – Eckpunkte des Diagramms void deikstra () ( int v [ SIZE ]; // Array von Beschriftungen int temp , i ; int minindex , min ; for (i = 0 ; i< SIZE ; i ++ ) { d [ i ] = INF ; // Das Pfadarray wird auf unendlich initialisiert v[i] = 1; ) d [ 0 ] = 0 ; Tun ( // Ausführung des Algorithmus minindex = INF ; min = INF ; für (i = 0 ; ich< SIZE ; i ++ ) { if ((v [ i ] == 1 ) && (d [ i ] < min )) { min = d [ i ]; minindex = i ; } } if (minindex != INF ) { for (i = 0 ; i < SIZE ; i ++ ) { if (a [ minindex ][ i ] >0 ) ( temp = min + a [ minindex ][ i ]; if (temp< d [ i ]) d [ i ] = temp ; } } v [ minindex ] = 0 ; } } while (minindex < INF ); }
Am Ende des Silvesterturniers beschloss der Sponsor, den Gewinnern Geschenke im Wert von $m$ per Post zu schicken. Wenn Sie die Anzahl der Teilnehmer $n$ und die Postzustellungszeit zwischen einigen Ukrposhta-Filialen kennen, ermitteln Sie die Mindestzeit, nach der der letzte Gewinner seinen Preis erhält.
Eingabedaten
Die erste Zeile enthält $3$-Zahlen: die Anzahl der Turnierteilnehmer $n$, die Anzahl der Sponsorenpreise $m$ und die Anzahl bekannter Lieferzeiten zwischen einigen Filialen $k$. Die nächste Zeile enthält die Nummern der Teilnehmer, die Gewinner wurden, getrennt durch ein Leerzeichen.
Als nächstes folgen $k$-Zeilen mit jeweils 3$-Zahlen mit Informationen über bekannte Lieferzeiten zwischen einigen Filialen im Format: $a$ $b$ $t$, wobei $a$ und $b$ Abteilungsnummern sind, $t $ $(0 \leqslant t \leqslant 365)$ – E-Mail-Zustellungszeit zwischen ihnen. Die letzte Zeile enthält eine einzelne Nummer – die Nummer der Postfiliale, von der aus der Sponsor die Preise verschickt. Es ist bekannt, dass $1 \leqslant n, m, a, b \leqslant 365$.
Ausgabe
Wenn alle Preise an die Teilnehmer ausgehändigt wurden, schreiben Sie in die erste Zeile „Der gute Sponsor!“ und in die nächste Zeile die Zeit, nach der der letzte Gewinner seinen Preis erhält. Wenn mindestens einer der Teilnehmer den Preis nicht erhält, schreiben Sie in einer Zeile „Der Sponsor ist nicht schuld...“ in die Zeile. Expressphrasen ohne Anführungszeichen.
Tests
| № | Eingabedaten | Ausgabe |
| 1. | 3 2 2 2 3 1 2 3 2 3 4 1 |
Der gute Sponsor! 7 |
| 2. | 5 1 4 5 1 3 2 2 3 3 4 2 5 4 5 6 1 |
Der gute Sponsor! 16 |
| 3. | 7 2 6 1 3 1 3 2 2 4 32 4 5 94 3 1 0 6 2 4 7 2 3 7 |
Es ist nicht die Schuld des Sponsors... |
| 4. | 5 2 6 1 2 3 1 1 3 4 2 2 4 3 5 1 4 4 5 5 2 3 7 2 |
Der gute Sponsor! 6 |
Wird geladen...