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

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

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.

To find the shortest path for n points and m edges, generally iterating n times can get the shortest path for all points.

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!