Heim > Artikel > Backend-Entwicklung > Implementieren Sie den Dijkstra-Algorithmus für den kürzesten Weg mit C++
Der Link-State-Routing-Algorithmus (LS-Algorithmus) der Netzwerkschicht, von denen einer unter Verwendung des Dijkstra-Algorithmus geschrieben ist . Einführung in „Einführung in Algorithmen“: Der Dijkstra-Algorithmus löst das Single-Source-Shortest-Path-Problem in einem gewichteten gerichteten Graphen. Dieser Algorithmus erfordert, dass die Gewichte aller Kanten nicht negativ sind.
Algorithmusidee
Wie in der Abbildung gezeigt, Es gibt 6 Punkte und 8 Kanten V= {1,2,3,4,5,6}
4. Aus dem Pfadarray können wir erkennen, dass der V-Konzentrationspunkt 2 zu diesem Zeitpunkt den kürzesten Pfad hat (der Wert ist 3), also sei u=2, dann S={1,2}, V={3,4,5,6}
Weil dis[3]=dis[2]+4 ⇒ 7=3+4
… 9 ⇒ 12=3+9
Weil dis[5]=12>dis[3]+1=7+1 ⇒ Sei dis[5]=dis[3]+1 =7+1=8
Weil dis[6]= ∞ >dis[3]+6=7+6 ⇒ Sei dis[6]=dis[6]+6=7+6=13
Weil dis[6]=13>dis[4]+7=5+7 ⇒ Sei dis[6]=dis[4] +7=5+7=12
Weil dis[6]=12>dis[5]+2=8 +2 ⇒ Sei dis[6]=dis[5]+2=8+2=10
Der kürzeste Weg von Punkt 1 zu jedem Punkt wird wie oben berechnet. Ich habe das Gefühl, dass der Text in letzter Zeit sehr chaotisch und schwer verständlich ist. Aber ich danke Ihnen allen, dass Sie das sehen konnten.
Finden Sie den kürzesten Weg in Bezug auf n Punkte und m Kanten. Im Allgemeinen kann der kürzeste Weg für alle Punkte durch n-maliges Iterieren ermittelt werden.
Jetzt einfach den Code posten, um zu provozieren
/* * @author Wenpupil * @time 2019-04-04 * @version 1.0 * @Description 最短路径之Dijkstra算法 关于无负权的无向图练习 */ #include<iostream> #include<cmath> #include<string.h> #define INIT 9999 using namespace std; int map[20][20]; //存储19个点的无向图 int s[20]; //标记数组 int dis[20]; void mDijkstra(int i,int m) { for(int i=0;i0){ dis[j]=min(dis[j],dis[u]+map[u][j]); } } } } int main(void) { int m,n; //共有m个点,n条边 cin>>m>>n; for(int i=0;i<n int cin>>x>>y>>z; map[x][y]=map[y][x]=z; } mDijkstra(1,m); //从节点1出发 遍历全图 for(int i=1;i<link href="https://csdnimg.cn/release/phoenix/mdeditor/markdown_views-258a4616f7.css" rel="stylesheet"> <!-- flowchart 箭头图标 勿删 --><svg xmlns="http://www.w3.org/2000/svg" style="display: none;"><path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"></path></svg><h2> <span style="font-size: 16px;">[Empfohlener Kurs: </span><a href="http://www.php.cn/course/list/38.html" target="_self" style="font-size: 16px; text-decoration: underline;"><span style="font-size: 16px;"> C++-Video-Tutorial</span></a><span style="font-size: 16px;">】</span> </h2></n></string.h></cmath></iostream>
Das obige ist der detaillierte Inhalt vonImplementieren Sie den Dijkstra-Algorithmus für den kürzesten Weg mit C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!