迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。
题源:最短路 - 蓝桥云课 (lanqiao.cn)
如下图所示,G 是一个无向图,其中蓝色边的长度是 1、橘色边的长度是 2、绿色边的长度是 3。
求从 A 到 S 的最短距离是多少?
#include <iostream>
#include <string.h>
#include <string>
using namespace std;
#define V 19
#define INF 0x3f
#define MIN 0x3f
int 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博客