Implement Dijkstra's algorithm for the shortest path using C++

The link state routing algorithm (LS algorithm) of the network layer, one of which is written using the Dijkstra algorithm . Introduction to "Introduction to Algorithms": Dijkstra's algorithm solves the single-source shortest path problem on a weighted directed graph. This algorithm requires that the weights of all edges are non-negative.

Algorithm idea

1. The G set represents all point sets, and the S set represents the shortest path from the source to a certain point that has been solved Point set, V set is expressed as a point set to find the shortest path
2. First let S=Ø, V=G

As shown in the figure, there are 6 points and 8 edges V={ 1,2,3,4,5,6}

3. Take u=1, put point 1 into S, S={1} ,V ={2,3,4,5,6}, traverse the points connected to point 1, and put the weights into the array
   

4. By path From the array, we can know that V concentration point 2 has the shortest path (value is 3) at this time, so let u=2, then S={1,2}, V={3,4,5,6}

Because dis[3]=dis[2] 4 ⇒ 7=3 4
… . dis[5]=dis[2] 9 ⇒ 12=3 9

5. Similarly, now S={1,2},V={3,4,5,6}, in V it is found that dis[3] is the minimum value except dis[1], dis[2] , so let S=S∪{3}
   At this time S={1,2,3}, V={4,5,6}

Because dis[5]=12>dis[3] 1=7 1 ⇒ Let dis[5]=dis[3] 1=7 1=8
because dis[6]=∞ >dis[3] 6= 7 6 ⇒ Let dis[6]=dis[6] 6=7 6=13

##Similarly, now S={1,2,3}, V={4,5,6}, it is found in V that dis[4] is the minimum value except dis[1], dis[2], dis[3], so let S=S∪{4}
6. 
   At this time S={1,2,3,4},V={5,6}
##Because dis[6]=13>dis[4] 7 =5 7 ⇒ Let dis[6]=dis[4] 7=5 7=12

7. At this time S={1,2,3,4,5},V={6}
   
because dis[6]=12> ;dis[5] 2=8 2 ⇒ Let dis[6]=dis[5] 2=8 2=10

The shortest path from point 1 to each point as above Just figure out the path. I feel like the writing lately is very messy and not easy to understand. But thank you all for being able to see this.

Now is the time to post the 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<br><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>##[Recommended course: </svg><h2>
<span style="font-size: 16px;"> C video tutorial</span><a href="//m.sbmmt.com/course/list/38.html" target="_self" style="font-size: 16px; text-decoration: underline;"><span style="font-size: 16px;">】</span></a>
</h2></n></string.h></cmath></iostream>

The above is the detailed content of Implement Dijkstra's algorithm for the shortest path using C++. For more information, please follow other related articles on the PHP Chinese website!