Dijkstra C艹板子

板子"/>

Dijkstra C艹板子

迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

题源：最短路 - 蓝桥云课 (lanqiao)

如下图所示，G 是一个无向图，其中蓝色边的长度是 1、橘色边的长度是 2、绿色边的长度是 3。

求从 A 到 S 的最短距离是多少？

#include <iostream>
#include <string.h>
#include <string>
using namespace std;#define V 19
#define INF 0x3f
#define MIN 0x3fint Min = MIN;
int dist[V]; //用来储存那些已经确定最短路径的顶点集合,dist[i]=dis表示从src到i的最短路长度为dis
bool vis[V]; //用来标记是否被访问的集合//默认图,零接矩阵表示，节点为A~Z
int G[V][V] = {};void add(char x,char y,int c)
{int a=x-'A';int b=y-'A';G[a][b]=G[b][a]=c;cout<<x<<"->"<<y<<":  "<<G[a][b]<<endl;
}void dijkstra(int G[V][V], char Src){//初始化memset(dist,0x3f,sizeof dist);memset(vis,false,sizeof vis);int src = int(Src-'A');int visit = -1;for(int i=0;i<V;i++){dist[i]=G[src][i];}//选出距离src最小的节点dist[src]=0;vis[visit]=true;for(int k=0;k<V;k++){Min = 0x3f;//记得更新for(int i=0;i<V;i++){if(!vis[i]&&(dist[i]<Min)){Min = dist[i];visit = i;}}vis[visit]=true;for(int j=0;j<V;j++){if(dist[visit]+G[visit][j] < dist[j])dist[j] = dist[visit]+G[visit][j];}}}void print_path(){}int main()
{memset(G,0x3f,sizeof G);for(int i=0;i<V;i++){G[i][i] = 0;}add('A','B',2);add('A','C',1);add('A','D',1);add('A','E',1);add('B','J',2);add('B','G',1);add('C','D',3);add('C','F',3);add('C','G',3);add('D','E',1);add('D','G',2);add('D','H',1);add('D','I',2);add('E','H',1);add('E','I',3);add('F','G',1);add('F','J',1);add('G','F',1);add('G','I',3);add('G','K',2);add('H','I',1);add('H','L',2);add('I','M',3);add('J','S',2);add('K','N',1);add('K','L',3);add('K','P',2);add('L','M',1);add('L','R',1);add('M','N',2);add('M','Q',1);add('M','S',1);add('N','P',1);add('O','P',1);add('O','Q',1);add('O','R',3);add('R','S',1);dijkstra(G,'A');for(int i=0;i<V;i++){cout<<dist[i]<<endl;}return 0;
}

References

 Dijkstra算法原理与实现_dijkstra算法伪代码_wangpenghnu的博客-CSDN博客

 Dijkstra算法及伪代码_dijkstra算法伪代码_在线找猹的博客-CSDN博客