Heim  >  Artikel  >  Backend-Entwicklung  >  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
little bottlenach vorne
2019-04-09 10:48:547605Durchsuche

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="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!

Stellungnahme:
Dieser Artikel ist reproduziert unter:csdn.net. Bei Verstößen wenden Sie sich bitte an admin@php.cn löschen