1、用邻接矩阵实现（待填坑。。。）

2、用邻接表实现

邻接表定义

#define MaxVertexnum 100 //最大顶点数量
int dis[MaxVertexnum] = { 0 }; //单源最短路径
bool vis[MaxVertexnum] = { 0 }; //访问标志位
#define INF 0x7fffffff //最大值
#define VertexType int //顶点类型
#define InfoType int //边权重类型
 
typedef struct ArcNode{
    int adjvex; //边指向结点
	InfoType info; //边权重
	struct ArcNode* next;
};
 
typedef struct VNode {
	VertexType name;
	ArcNode* first;
}AdjList[MaxVertexnum];
 
typedef struct {
	AdjList node;
	int vexnum;
	int arcnum;
}ALGraph;

具象理解，一共三种结构相互连接，可以类比树的孩子兄弟表示法以及散列表，三者有异曲同工之妙

 dijkstra实现

1. 先在当前dis[]距离列表中找到未被访问且距离最小的点u
2. 如果没有找到则代表所有点最短距离都已经计算完毕
3. 若找到则取出u的所有邻接点，进行最短距离计算并更新
4. 回到步骤(1)继续执行，直到运行完毕

void dijkstra(ALGraph* G, int start) {
	fill(vis, vis + MaxVertexnum, 0); //访问标志初始化
	fill(dis, dis + MaxVertexnum, INF); //路径初始化
	dis[start] = 0; //源点到自己的距离为0
	int i, j, u, min;
	for (i = 0; i < G->vexnum; i++) {
		u = -1; //在未被访问过的顶点中找到距离最短的点
		min = INF;
		for (j = 1; j <= G->vexnum; j++) {  
			if (vis[j] = false && dis[j] < min) {
				u = j; 
				min = dis[j];
			}
		}
		if (u == -1) return; //所有顶点均已访问
		vis[u] = true;
		ArcNode* tmp = G->node[u].first; //找到距离最短的顶点u的邻接点
		printf("\n\n\n");
		while (tmp) {
			//若该邻接点未被访问过 且 源点到u的最短距离+u到该邻接点的距离小于该邻接点此前的最短距离
			if (vis[tmp->adjvex] == false && dis[u] + tmp->info < dis[tmp->adjvex]) 
				dis[tmp->adjvex] = dis[u] + tmp->info;
			tmp = tmp->next; //继续访问u的下一个邻接点
		}
	}
 
}

 3、抽象实现Dijkstra算法模板（用于做题）

#include 
using namespace std;
struct node {
	int id, dis;
	bool friend operator < (const node& a, const node& b) {
		return a.dis > b.dis;
	}
};
int n, m, s;
int ui, vi, wi;
vectorint, int>> E[100];
int dis[100];
int vis[100];
void dijkstra() {
	fill(dis, dis + 100, 1e9); //初始化dis列表
	dis[s] = 0;
	priority_queue Q;
	Q.push(node{ s, 0 });
	while (!Q.empty()) {
		int Now = Q.top().id; //当前Now顶点的距离最短
		int D = Q.top().dis; //D为Now顶点目前的最短距离
		Q.pop();
		//对应底下①语句，因每次更新数据都会把距离放进列表，故当计算完所有距离后依旧留下一堆无用数据，用此语句进行过滤
		if (vis[Now]) continue; 
		vis[Now] = 1;
		for (auto it : E[Now]) { //访问Now的所有邻边
			int des = it.first;
			int weigh = it.second;
			if (dis[des] > D + weigh) { //源点到Now的距离+Now到des的距离 < 先前des的最短距离
				dis[des] = D + weigh;
				Q.push(node{ des, dis[des] }); //①
			}
		}
	}
}
int main() {
	cin >> n >> m >> s; //n：顶点数	m：边数，s：源点
	for (int i = 0; i < m; i++) {
		cin >> ui >> vi >> wi; //从ui到vi权重为wi的一条边
		E[ui].push_back({ vi,wi });
	}
	dijkstra();
	for (int i = 1; i <= n; i++) {
		printf("%d ", dis[i]);
	}
 
	return 0;
}

 可由下图具象理解模板

 若要得到此图应如此输入数据，对比输入数据与上图右方抽象结构，你就可以发现内在联系

5 8 0
0 1 1
0 2 2
0 4 1
2 1 3
2 3 2
2 4 2
3 4 1
3 1 2

输入输出样例

 输入 #1

4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

输出 #1

0 2 4 3