22 Dijkstra 算法（严 7.42）

本文主要是介绍22 Dijkstra 算法（严 7.42），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目

description：
编写程序，实现以邻接表作存储结构，求从源点到其余各顶点的最短路径的 Dijkstra算法。
input：
第一行输入顶点数 n 和边数 m；第二行输入顶点信息；分 m 行输入 m 对顶点 vi，vj（表示由顶点 vi 到顶点 vj（i 不等于 j）的边）以及该弧的权值。
output：
输出从源点到其余各顶点的最短路径（不可达用-1 表示）。
sample_input：
6 11
1 2 50
1 3 10
1 5 45
2 3 15
2 5 10
3 1 20
3 4 15
4 2 20
4 5 35
5 4 30
6 4 3
sample_output：
1 3 10
1 4 25
1 2 45
1 5 45
1 6 -1

思路

1. 以邻接表作存储结构

/*边表*/
typedef struct ArcNode {
	int adjvex; //该弧指向顶点的位置
	int weight;//权值
	struct ArcNode *nextarc; //指向下一条弧的指针
} ArcNode;

/*顶点表*/
typedef struct VertexNode {
	int data; //顶点数据
	ArcNode *firstarc; //指向该顶点第一条弧的指针
} VertexNode;

/*基于邻接表的图*/
typedef struct AdjList {
	VertexNode vertex[MAX];
	int vexnum, arcnum; //图的顶点数和弧数
} AdjList;

void createAdjList(AdjList *L, int n, int m) {
	int i, j;
	L->vexnum = n;
	L->arcnum = m;
	for (i = 0; i < n; i++) { //输入顶点信息，初始化顶点表
		L->vertex[i].data = i + 1; //1-6
		L->vertex[i].firstarc = NULL;
	}
	int a, b, c; //a记录源点，b记录目标点，c记录权值
	for (j = 0; j < m; j++) { //输入边的信息，存储在边表中
		cin >> a >> b >> c;
		ArcNode *N = (ArcNode *)malloc(sizeof(ArcNode));
		N->adjvex = b;
		N->weight = c;
		N->nextarc = L->vertex[a - 1].firstarc; //头插法
		L->vertex[a - 1].firstarc = N;
	}
}

如下图所示：

第一步：建立顶点表，如上图红色部分；

for (i = 0; i < n; i++) { //输入顶点信息，初始化顶点表
		L->vertex[i].data = i + 1; //1-6
		L->vertex[i].firstarc = NULL;
	}

第二步，挨个输入创建结点，如上图绿色部分；

cin >> a >> b >> c;
ArcNode *N = (ArcNode *)malloc(sizeof(ArcNode));
N->adjvex = b;
N->weight = c;

第三步，将上一步创建的结点按头插法插入

N->nextarc = L->vertex[a - 1].firstarc; //头插法
L->vertex[a - 1].firstarc = N;

代码

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#define MAX 100
using namespace std;

/*边表*/
typedef struct ArcNode {
	int adjvex; //该弧指向顶点的位置
	int weight;//权值
	struct ArcNode *nextarc; //指向下一条弧的指针
} ArcNode;

/*顶点表*/
typedef struct VertexNode {
	int data; //顶点数据
	ArcNode *firstarc; //指向该顶点第一条弧的指针
} VertexNode;

/*基于邻接表的图*/
typedef struct AdjList {
	VertexNode vertex[MAX];
	int vexnum, arcnum; //图的顶点数和弧数
} AdjList;

void createAdjList(AdjList *L, int n, int m);
void Dijkstra(AdjList *L, int n, int m);

int main() {
	int m, n; //n为顶点数，m为边数
	cin >> n >> m;

	AdjList *list;
	list = (AdjList *)malloc(sizeof(AdjList));
	createAdjList(list, n, m);

	Dijkstra(list, n, m);
	return 0;
}

void createAdjList(AdjList *L, int n, int m) {
	int i, j;
	L->vexnum = n;
	L->arcnum = m;
	for (i = 0; i < n; i++) { //输入顶点信息，初始化顶点表
//		cin >> L->vertex[i].data;
		L->vertex[i].data = i + 1; //1-6
		L->vertex[i].firstarc = NULL;
	}
	int a, b, c; //a记录源点，b记录目标点，c记录权值
	for (j = 0; j < m; j++) { //输入边的信息，存储在边表中
		cin >> a >> b >> c;
		ArcNode *N = (ArcNode *)malloc(sizeof(ArcNode));
		N->adjvex = b;
		N->weight = c;
		N->nextarc = L->vertex[a - 1].firstarc; //头插法
		L->vertex[a - 1].firstarc = N;
	}

	/*test*/
//	for (i = 0; i < n; i++) {
//		cout << i << ":" << L->vertex[i].data << " " << L->vertex[i].firstarc->adjvex << endl;
//	}
}

void Dijkstra(AdjList *L, int n, int m) {
	int i, j;
	int k = 0;//当前访问结点，初始为0
	int r = 0;//之前的路径长度，初始为0
	/*初始化*/
	int dij[4][n];
	for (i = 0; i < n; i++)
		dij[0][i] = 0; //记录是否访问过
	for (i = 0; i < n; i++)
		dij[1][i] = MAX; //记录权值
	for (i = 0; i < n; i++)
		dij[2][i] = -1; //记录是否存在路径
	for (i = 0; i < n; i++)
		dij[3][i] = 0; //记录是否输出过
	dij[1][0] = 0;
	/*Dijkstra*/
	for (i = 0; i < n; i++) { //总循环次数
		dij[0][k] = 1;
		ArcNode *w = L->vertex[k].firstarc; //指针，设w为v的第一个邻接点
		while (w) {
			int t = w->adjvex;
			if (dij[0][t - 1] == 0) { //仅更新未访问结点
				if (r + w->weight < dij[1][t - 1]) {
					dij[1][t - 1] = r + w->weight; //更新最短路径
					dij[2][t - 1] = k + 1; //更新上一个结点
				}
			}
			w = w->nextarc;
		}
		/*寻找未访问结点中的最短路径*/
		int min = MAX;
		for (int i = 1; i < n; i++) {
			if (dij[0][i] == 0) {
				if (dij[1][i] < min) {
					min = dij[1][i];
					k = i;
					r = min;
				}
			}
		}
	}
	/*按路径长使结果从小到大输出*/
	for (i = 1; i < n; i++) {
		int M = MAX;
		int temp = 0;
		if (dij[2][i] == -1)
			cout << L->vertex[0].data << " " << L->vertex[i].data << " " << "-1" << endl;
		else {
			for (int j = 1; j < n; j++) {
				if (dij[3][j] == 0) {
					if (dij[1][j] < M) {
						M = dij[1][j];
						temp = j;
					}
				}
			}
			cout << L->vertex[0].data << " " << L->vertex[temp].data << " " << dij[1][temp] << endl;
			dij[3][temp] = 1;//记录已输出的结点
		}
	}
}

这篇关于22 Dijkstra 算法（严 7.42）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！