Implémentez l'algorithme de Dijkstra pour le chemin le plus court en utilisant C++

L'algorithme de routage par état de lien (algorithme LS) de la couche réseau, dont l'un est écrit à l'aide de l'algorithme de Dijkstra . Introduction à « Introduction aux algorithmes » : l'algorithme de Dijkstra résout le problème du chemin le plus court à source unique sur un graphe orienté pondéré. Cet algorithme nécessite que les poids de toutes les arêtes soient non négatifs.

Idée d'algorithme

1. L'ensemble G représente tous les ensembles de points, et l'ensemble S représente le chemin le plus court de la source à un certain point qui a été résolu Ensemble de points, V ensemble est exprimé sous la forme d'un ensemble de points pour trouver le chemin le plus court
2. Laissez d'abord S=Ø, V=G

Comme le montre la figure, il y a 6 points et 8 arêtes V= {1,2,3,4,5,6}

3. Prendre u=1, mettre le point 1 dans S , S={1}, V={2,3,4,5,6}, parcourez les points connectés au point 1 et mettez les poids dans le tableau
   

4. Par À partir du tableau de chemins, nous pouvons savoir que le point de concentration V 2 a le chemin le plus court (la valeur est 3) à ce moment, alors laissez u=2, puis S={1,2}, V= {3,4,5,6}

Parce que dis[3]=dis[2]+4 ⇒ 7=3+4
… . 12=3+9

5. De même, maintenant S={1,2},V={3,4,5,6}, trouver dis[3 ] dans V est la division de dis[1], dis[2 ], donc soit S=S∪{3}
   À ce moment, S={1,2,3}, V={4 ,5,6}

Parce que dis[5]=12>dis[3]+1=7+1 ⇒ Soit dis[5]=dis[3]+1=7 +1=8
Parce que dis[6]= ∞ >dis[3]+6=7+6 ⇒ Soit dis[6]=dis[6]+6=7+6=13

6. De la même manière, maintenant S={1,2,3}, V={4,5,6}, dans V on trouve que dis[4] est la plus petite sauf la valeur dis[1], dis[2], dis[3], alors laissez S=S∪{4}
   À ce moment, S={1,2,3,4}, V={5,6}

Parce que dis[6]=13>dis[4]+7=5+7 ⇒ Soit dis[6]=dis[4]+7 =5+7=12

7. De même, maintenant S={1,2,3,4}, V={5,6}, trouver dis[ 5] dans V est l'ajout de dis[1], dis[2], dis[ 3], la valeur minimale en dehors de dis[4], alors laissez S=S∪{5}
   À ce moment , S={1,2,3,4,5}, V={6}

Parce que dis[6]=12>dis[5]+2=8+2 ⇒ Soit dis[6]=dis[5]+2=8+2=10

Le chemin le plus court du point 1 à chaque point est calculé comme ci-dessus, je pense. que l'écriture récente est très brouillonne et difficile à comprendre. Mais merci à tous d'avoir pu voir ça.
Trouver le chemin le plus court par rapport à n points et m arêtes Généralement, le chemin le plus court pour tous les points peut être obtenu en itérant n fois.
Il est maintenant temps de publier le code

/*
 * @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;">[Cours recommandé : </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;">Tutoriel vidéo C++</span></a><span style="font-size: 16px;">】</span>
</h2></n></string.h></cmath></iostream>

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!