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

1. G-Satz repräsentiert alle Punktmengen und S-Satz repräsentiert den kürzesten Weg von der Quelle zu einem bestimmten Punkt Das wurde gelöst Punktsatz, V-Satz wird als Punktsatz ausgedrückt, um den kürzesten Weg zu finden
2. Zuerst sei S=Ø, V=G

Wie in der Abbildung gezeigt, Es gibt 6 Punkte und 8 Kanten V= {1,2,3,4,5,6}

3. Nimm u=1, setze Punkt 1 in S , S={1}, V={2,3,4,5,6}, durchquere die mit Punkt 1 verbundenen Punkte und füge die Gewichte in das Array ein
   

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

5. In ähnlicher Weise gilt nun S={1,2},V={3,4,5,6} und es wird dis gefunden [3] in V ist die Addition von dis[1], dis[2 ], also sei S=S∪{3}
   Zu diesem Zeitpunkt ist S={1,2,3}, V= {4,5,6}

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

6. Auf die gleiche Weise, jetzt S={1,2,3}, V={4,5,6}, wird in V gefunden, dass dis[4 ] ist der kleinste außer dis[1], dis[2], dis[3] Wert, also sei S=S∪{4}
   Zu diesem Zeitpunkt ist S={1,2,3,4 }, V={5,6}

Weil dis[6]=13>dis[4]+7=5+7 ⇒ Sei dis[6]=dis[4] +7=5+7=12

7. Ähnlich gilt nun S={1,2,3,4}, V={5,6}, Befund dis[5] in V ist die Addition von dis[1], dis[2], dis[ 3], dem Minimalwert außerhalb von dis[4], also sei S=S∪{5}
   At Diesmal ist S={1,2,3,4,5}, V={6}

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!