Dijkstra 迪杰斯特拉算法

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法(单源最短路)。

迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。
朴素Dijkstra时间复杂度o(n^2)。
优先队列优化Dijkstra时间复杂度为 o(m log n)。

测试数据

1
6 8
1 2 3 4 5 6
1 3 10
1 5 30
1 6 100
2 3 5
3 4 50
4 6 10
5 4 20
5 6 60

测试输出

0
1061109567
10
50
30
60

Dijkstra代码

typedef bool PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
bool final[MAX_VERTEX_NUM];
typedef int ShortPathTable[MAX_VERTEX_NUM];

void ShortestPath_DIJ(MGraph G, int v0, PathMatrix& P, ShortPathTable& D)
{
	//用Dijkstra算法求有向网G的v0顶点到其余顶点的最短路径p[v]及带权长度D[v]
	//若P[v][w]为TRUE，则w是从v0到v当前求得最短路径上的顶点
	//final[v]为TRUE当且仅当v属于s，即已求得从v0到v的最短路径
	int v, min;
	for (v = 0; v < G.vexnum; v++) {
		final[v] = false; D[v] = G.arcs[v0][v].adj;
		for (int w = 0; w < G.vexnum; w++) P[v][w] = false;//设空路径
		if (D[v] < INFINITY) { P[v][v0] = true; P[v][v] = true; }
	}
	//初始化v0属于s集
	D[v0] = 0; final[v0] = true;
	for (int i = 1; i < G.vexnum; i++) {//其余G.vexnum - 1个顶点
		min = INFINITY;//当前所知离v0点最近距离
		for (int w = 0; w < G.vexnum; w++) {
			if(!final[w])
				if (D[w] < min) { v = w; min = D[w]; }
		}
		final[v] = true;
		for (int w = 0; w < G.vexnum; w++) {
			if (!final[w] && (min + G.arcs[v][w].adj < D[w])) {
				D[w] = min + G.arcs[v][w].adj;
				for (int i = 0; i < G.vexnum; i++) P[w][i] = P[v][i];
				P[w][w] = true;//P[w] = P[v] + [w]
			}
		}
	}
}

完整代码

#include<iostream>
#include<climits>
#include<string>
#include<cstdlib> 
using namespace std;
#define ERROR -1

#define MAX_VERTEX_NUM 20 //最多顶点个数 
#define INFINITY 0x3f3f3f3f //最大值 
typedef enum { DG, DN, UDG, UDN } GraphKind; //有向图、有向网、无向图、无向网
typedef int VRType, Status;
typedef string VertexType;

typedef struct ArcCell {
	VRType adj; //VRType是顶点关系类型。对无权图用0
				//表示相邻否；对带权图则为权值类型
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct {
	VertexType vexs[MAX_VERTEX_NUM]; //顶点向量 
	AdjMatrix arcs; //邻接矩阵 
	int vexnum, arcnum; //图的当前顶点数和弧数 
	int kind;
}MGraph;

//根据映射定位下标 
int LocateVex(MGraph G, VertexType v)
{
	for (int i = 0; i < G.vexnum; i++) {
		if (v == G.vexs[i]) return i;
	}
	return ERROR;
}

Status CreateDG(MGraph& G)//有向图 
{
	cout << "请输入顶点数和弧数：\n";
	cin >> G.vexnum >> G.arcnum;
	for (int i = 0; i < G.vexnum; i++) {
		cout << "请输入向量信息：\n";
		cin >> G.vexs[i];
	}

	for (int i = 0; i < G.vexnum; i++) {
		for (int j = 0; j < G.vexnum; j++) {
			G.arcs[i][j].adj = INFINITY;
		}
	}

	VertexType v, u; // 出发点 目标点 
	for (int k = 0; k < G.arcnum; k++) {
		cout << "请输入第" << k + 1 << "条弧的信息（v,u）：\n";
		cin >> v >> u;
		int i = LocateVex(G, v);
		int j = LocateVex(G, u);
		G.arcs[i][j].adj = 1;
	}
	return 1;
}

Status CreateDN(MGraph& G)//有向网 
{
	cout << "请输入顶点数和弧数：\n";
	cin >> G.vexnum >> G.arcnum;
	for (int i = 0; i < G.vexnum; i++) {
		cout << "请输入向量信息：\n";
		cin >> G.vexs[i];
	}

	for (int i = 0; i < G.vexnum; i++) {
		for (int j = 0; j < G.vexnum; j++) {
			G.arcs[i][j].adj = INFINITY;
		}
	}

	VertexType v, u; // 出发点 目标点 
	for (int k = 0; k < G.arcnum; k++) {
		cout << "请输入第" << k + 1 << "条弧的信息（v,u）：\n";
		cin >> v >> u;
		int i = LocateVex(G, v);
		int j = LocateVex(G, u);
		cout << "请输入包含的额外信息(边权)：\n";
		cin >> G.arcs[i][j].adj;
	}
	return 1;
}

Status CreateUDG(MGraph& G)//无向图 
{
	cout << "请输入顶点数和弧数：\n";
	cin >> G.vexnum >> G.arcnum;
	for (int i = 0; i < G.vexnum; i++) {
		cout << "请输入向量信息：\n";
		cin >> G.vexs[i];
	}

	for (int i = 0; i < G.vexnum; i++) {
		for (int j = 0; j < G.vexnum; j++) {
			G.arcs[i][j].adj = INFINITY;
		}
	}

	VertexType v, u; // 出发点 目标点 
	for (int k = 0; k < G.arcnum; k++) {
		cout << "请输入第" << k + 1 << "条弧的信息（v,u）：\n";
		cin >> v >> u;
		int i = LocateVex(G, v);
		int j = LocateVex(G, u);
		G.arcs[i][j].adj = G.arcs[j][i].adj = 1;
	}
	return 1;
}

Status CreateUDN(MGraph& G)//无向网 
{
	cout << "请输入顶点数和弧数：\n";
	cin >> G.vexnum >> G.arcnum;
	for (int i = 0; i < G.vexnum; i++) {
		cout << "请输入第" << i + 1 << "向量信息：\n";
		cin >> G.vexs[i];
	}

	for (int i = 0; i < G.vexnum; i++) {
		for (int j = 0; j < G.vexnum; j++) {
			G.arcs[i][j].adj = INFINITY;
		}
	}

	VertexType v, u; // 出发点 目标点 
	int w; // 权重 
	for (int k = 0; k < G.arcnum; k++) {
		cout << "请输入第" << k + 1 << "条弧的信息（v,u）：\n";
		cin >> v >> u;
		int i = LocateVex(G, v);
		int j = LocateVex(G, u);
		cout << "请输入包含的额外信息(边权)：\n";
		cin >> G.arcs[i][j].adj;
		G.arcs[j][i].adj = G.arcs[i][j].adj;
	}
	return 1;
}

Status CreateGraph(MGraph& G)
{
	cin >> G.kind;
	switch (G.kind)
	{
	case DG:return CreateDG(G);
	case DN:return CreateDN(G);
	case UDG:return CreateUDG(G);
	case UDN:return CreateUDN(G);
	default: return ERROR;
	}
}//CreateGraph

void TraveGraph(MGraph G)
{
	for (int i = 0; i < G.vexnum; i++) {
		for (int j = 0; j < G.vexnum; j++) {
			cout << G.arcs[i][j].adj << ' ';
		}
		cout << '\n';
	}
}
typedef bool PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
bool final[MAX_VERTEX_NUM];
typedef int ShortPathTable[MAX_VERTEX_NUM];

void ShortestPath_DIJ(MGraph G, int v0, PathMatrix& P, ShortPathTable& D)
{
	//用Dijkstra算法求有向网G的v0顶点到其余顶点的最短路径p[v]及带权长度D[v]
	//若P[v][w]为TRUE，则w是从v0到v当前求得最短路径上的顶点
	//final[v]为TRUE当且仅当v属于s，即已求得从v0到v的最短路径
	int v, min;
	for (v = 0; v < G.vexnum; v++) {
		final[v] = false; D[v] = G.arcs[v0][v].adj;
		for (int w = 0; w < G.vexnum; w++) P[v][w] = false;//设空路径
		if (D[v] < INFINITY) { P[v][v0] = true; P[v][v] = true; }
	}
	//初始化v0属于s集
	D[v0] = 0; final[v0] = true;
	for (int i = 1; i < G.vexnum; i++) {//其余G.vexnum - 1个顶点
		min = INFINITY;//当前所知离v0点最近距离
		for (int w = 0; w < G.vexnum; w++) {
			if(!final[w])
				if (D[w] < min) { v = w; min = D[w]; }
		}
		final[v] = true;
		for (int w = 0; w < G.vexnum; w++) {
			if (!final[w] && (min + G.arcs[v][w].adj < D[w])) {
				D[w] = min + G.arcs[v][w].adj;
				for (int i = 0; i < G.vexnum; i++) P[w][i] = P[v][i];
				P[w][w] = true;//P[w] = P[v] + [w]
			}
		}
	}
}

int main()
{
	MGraph G;
	cout << "请输入要创建的图的类型（有向图 0、有向网 1、无向图 2、无向网 3）：\n";
	CreateGraph(G);
	//TraveGraph(G);
	PathMatrix P;
	ShortPathTable D;
	ShortestPath_DIJ(G, 0, P, D);
	for (int i = 0; i < G.vexnum; i++) {
		cout << D[i] << endl;
	}
	return 0;
}