图的最短路径之Dijkstra算法C/C++代码实现

朴灿烈づ我的快乐病毒、 2023-02-19 14:27 27阅读 0赞

## 迪杰斯特拉Dijkstra算法： ##

该算法用来求解从某个源点到其余各顶点的最短路径

以该图为例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]  
其邻接矩阵为：  
![在这里插入图片描述][20200621094501926.png]  
最短路径为：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 1]

## 具体过程： ##

算法中用到了三个辅组数组：  
S\[i\]：布尔值记录到顶点最短路径是否已经被确定  
Path\[i\]:记录顶点最短路径的直接前驱顶点序号  
D\[i\]:记录最短路径的长度，初值为权值  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 2]  
（上表中的i表示循环次数）

每次从D数组中选择最小的加入到S集合，紧接着用刚加入的顶点和个顶点比较如果路径变小了则更新相应D数组

## 代码如下： ##

#include<stdio.h>
    
    
    #define MaxInt 999			//定义无穷大
    #define MVNum 100
    typedef char VerTexType;    //顶点类型
    typedef int ArcType;		//边权值类型
    
    //邻接矩阵存储结构
    typedef struct
    {
        
    	VerTexType vexs[MVNum];				//顶点表
    	ArcType arcs[MVNum][MVNum];			//邻接矩阵
    	int vexnum, arcnum;					//图的当前点数和边数
    }AMGraph;
    
    void printGraph(AMGraph G);
    int LocateVex(AMGraph G, char v);
    
    //创建有向网
    void CreateUDN(AMGraph &G)
    {
        
    	G.vexnum = 6;						//输入总顶点数和边数
    	G.arcnum = 8;
    	G.vexs[0] = 'v0';					//输入顶点信息
    	G.vexs[1] = 'v1';
    	G.vexs[2] = 'v2';
    	G.vexs[3] = 'v3';
    	G.vexs[4] = 'v4';
    	G.vexs[5] = 'v5';
    
    	for (int i = 0; i < G.vexnum; i++)			//初始化邻接矩阵为极大值
    	{
        
    		for (int j = 0; j < G.vexnum; j++)
    		{
        
    			G.arcs[i][j] = MaxInt;
    		}
    	}
    
    	//输入权值
    	int i, j;
    	i = LocateVex(G, 'v0');
    	j = LocateVex(G, 'v2');
    	G.arcs[i][j] = 10;
    	i = LocateVex(G, 'v0');
    	j = LocateVex(G, 'v4');
    	G.arcs[i][j] = 30;
    	i = LocateVex(G, 'v0');
    	j = LocateVex(G, 'v5');
    	G.arcs[i][j] = 100;
    	i = LocateVex(G, 'v1');
    	j = LocateVex(G, 'v2');
    	G.arcs[i][j] = 5;
    	i = LocateVex(G, 'v2');
    	j = LocateVex(G, 'v3');
    	G.arcs[i][j] = 50;
    	i = LocateVex(G, 'v3');
    	j = LocateVex(G, 'v5');
    	G.arcs[i][j] = 10;
    	i = LocateVex(G, 'v4');
    	j = LocateVex(G, 'v3');
    	G.arcs[i][j] = 20;
    	i = LocateVex(G, 'v4');
    	j = LocateVex(G, 'v5');
    	G.arcs[i][j] = 60;
    
    	printGraph(G);
    }
    
    //返回顶点在数组中的下标
    int LocateVex(AMGraph G, char v)
    {
        
    	for (int i = 0; i < G.vexnum; i++)
    	{
        
    		if (G.vexs[i] == v)
    		{
        
    			return i;
    		}
    	}
    }
    
    //打印输出邻接矩阵
    void printGraph(AMGraph G)
    {
        
    	for (int i = 0; i < G.vexnum; i++)
    	{
        
    		printf("v%d :", i + 1);
    
    		for (int j = 0; j < G.vexnum; j++)
    		{
        
    			printf("%5d ", G.arcs[i][j]);
    		}
    		printf("\n");
    	}
    }
    
    //邻接矩阵深度优先遍历
    bool visited[MVNum];
    void DFS_AM(AMGraph G, int v)
    {
        
    	printf("v%c->", G.vexs[v]);
    	visited[v] = true;
    	for (int w = 0; w < G.vexnum; w++)
    	{
        
    		if ((G.arcs[v][w]) != 0 && (!visited[w]))
    		{
        
    			DFS_AM(G, w);
    		}
    	}
    }
    
    
    //最短路径迪杰斯特拉算法
    bool S[MVNum];				//判断v0到vi是否已经被确定最短路径长度
    int D[MVNum];				//存放v0到vi的最短路径长度值
    int Path[MVNum];			//存放vi的直接前驱顶点序号
    void ShortestPath_DIJ(AMGraph G, int v0)
    {
        
    	//初始化
    	int n = G.vexnum;		//图的顶点数
    	for (int v = 0; v< n; v++)
    	{
        
    		S[v] = false;
    		D[v] = G.arcs[v0][v];
    		if (D[v]<MaxInt)	//如果v0到v有路径，则Path数组置为v0
    		{
        
    			Path[v] = v0;
    		}
    		else {
        				//否则置为-1
    			Path[v] = -1;
    		}
    	}
    	S[v0] = true;
    	D[v0] = 0;
    
    
    	//算法开始
    	for (int i = 1; i < n; i++)
    	{
        
    		int min = MaxInt;
    		int v = 0;
    		//查找D[]中权值最小的且加入到完成集合S
    		for (int w = 0; w <n; w++)
    		{
        
    			if (!S[w] && D[w] < min)
    			{
        
    				v = w;			//最小的序号存入v中
    				min = D[w];		//最小权值存入min
    			}
    		}
    		S[v] = true;
    
    
    
    		//完成集合S添加新顶点后更新最短路径信息
    		for (int w = 0; w < n; w++)
    		{
        
    			if (!S[w] && (D[v] + G.arcs[v][w] < D[w]))
    			{
        
    				D[w] = D[v] + G.arcs[v][w];
    				Path[w] = v;
    			}
    		}
    
    
    		//逆序输出最短路径
    		int t = v;
    		while (Path[t] != -1)
    		{
        
    			printf("v%c<— ", G.vexs[t]);
    			t = Path[t];
    		}
    		printf("v0\n");
    	}
    }
    
    
    int main()
    {
        
    	AMGraph G;
    	CreateUDN(G);
    
    	int v = 0;
    	printf("深度优先遍历：：");
    	DFS_AM(G, v);
    
    	int v0 = 0;
    	printf("\n====================================\n");
    	printf("v0到各顶点的最短路径：\n");
    	ShortestPath_DIJ(G, v0);
    }

## 运行结果： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200621094403365.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70
[20200621094501926.png]: https://img-blog.csdnimg.cn/20200621094501926.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200621094538774.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200621095137554.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200621124356467.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70