Heim > Backend-Entwicklung > C#.Net-Tutorial > Implementieren Sie den Dijkstra-Algorithmus für den kürzesten Weg mit C++

Implementieren Sie den Dijkstra-Algorithmus für den kürzesten Weg mit C++

little bottle
Freigeben: 2019-04-09 10:53:52
nach vorne
7646 Leute haben es durchsucht

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}
Implementieren Sie den Dijkstra-Algorithmus für den kürzesten Weg mit C++Implementieren Sie den Dijkstra-Algorithmus für den kürzesten Weg mit C++

  1. 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
    Implementieren Sie den Dijkstra-Algorithmus für den kürzesten Weg mit C++Implementieren Sie den Dijkstra-Algorithmus für den kürzesten Weg mit C++

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
Implementieren Sie den Dijkstra-Algorithmus für den kürzesten Weg mit C++Implementieren Sie den Dijkstra-Algorithmus für den kürzesten Weg mit C++

  1. 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
Implementieren Sie den Dijkstra-Algorithmus für den kürzesten Weg mit C++Implementieren Sie den Dijkstra-Algorithmus für den kürzesten Weg mit C++

  1. 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
Implementieren Sie den Dijkstra-Algorithmus für den kürzesten Weg mit C++Implementieren Sie den Dijkstra-Algorithmus für den kürzesten Weg mit C++

  1. Ä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
Implementieren Sie den Dijkstra-Algorithmus für den kürzesten Weg mit C++Implementieren Sie den Dijkstra-Algorithmus für den kürzesten Weg mit C++

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="//m.sbmmt.com/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>
Nach dem Login kopieren

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!

Verwandte Etiketten:
Quelle:csdn.net
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Neueste Artikel des Autors
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage