C语言实现Dijkstra算法

C语言实现Dijkstra算法

题目实例：
给一个n(1 ≤ n ≤ 2500) 个点 m(1 ≤ m ≤ 6200) 条边的无向图，求 s 到 t 的最短路。

输入格式:
第一行四个由空格隔开的整数 n、m、s、t。

之后的 m 行，每行三个正整数 si​、ti​、wi​(1≤wi​≤109)，表示一条从si​ 到 ti​ 长度为 wi​ 的边。

输出格式:
一个整数，表示从s 到t 的最短路径长度。数据保证至少存在一条道路。

输入样例:
7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1
结尾无空行

输出样例:
7
 

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#define INFINITY  65535
#define MaxVertexNum 2500
int dist[MaxVertexNum], path[MaxVertexNum]
, collected[MaxVertexNum];
int s, t;
typedef struct GNode* PtrToGNode;
struct GNode {
	int Nv;
	int Ne;
	int G[MaxVertexNum][MaxVertexNum];
};
typedef PtrToGNode MGraph;
typedef struct ENode* PtrToENode;
struct ENode {
	int V1, V2;
	int Weight;
};
typedef PtrToENode Edge;
MGraph CreateGraph(int VertexNum) {
	int V, W;
	MGraph Graph;
	Graph = (MGraph)malloc(sizeof(struct GNode));
	Graph->Nv = VertexNum;
	Graph->Ne = 0;
	for (V = 1; V <= Graph->Nv; V++)
		for (W = 1; W <= Graph->Nv; W++)
			Graph->G[V][W] = INFINITY;
	return Graph;
}
void InsertEdge(MGraph Graph, Edge E) {
	Graph->G[E->V1][E->V2] = E->Weight;
	Graph->G[E->V2][E->V1] = E->Weight;
}
MGraph BuildGraph() {
	MGraph Graph;
	Edge E;
	int V,Nv,i;
	scanf("%d", &Nv);
	Graph = CreateGraph(Nv);
	scanf("%d", &(Graph->Ne));
	scanf("%d%d", &s, &t);
	if (Graph->Ne != 0) {
		E = (Edge)malloc(sizeof(struct ENode));
		for (i = 0; i < Graph->Ne; i++) {
			scanf("%d%d%d", &E->V1, &E->V2, &E->Weight);
			InsertEdge(Graph, E);
		}
	}
	return Graph;
}
int FindMinDist(MGraph Graph, int dist[], int collected[]) {
	int MinV, V;
	int MinDist = INFINITY;
	for(V = 1; V <= Graph->Nv; V++) {
		if (collected[V] == false && dist[V] < MinDist) {
			MinDist = dist[V];
			MinV = V;
		}
	}
	if (MinDist < INFINITY)
		return MinV;
	else return -1;
}
bool Dijkstra(MGraph Graph, int dist[], int path[], int S) {
	int V, W;
	for (V = 1; V <= Graph->Nv; V++) {
		dist[V] = Graph->G[S][V];
		if (dist[V] < INFINITY)
			path[V] = S;
		else
			path[V] = -1;
		collected[V] = false;
	}
	dist[S] = 0;
	collected[V] = true;
	while (1) {
		V = FindMinDist(Graph, dist, collected);
		if (V == -1)
			break;
		collected[V] = true;
		for(W=1;W<=Graph->Nv;W++)
			if (collected[W] == false && Graph->G[V][W] < INFINITY) {
				if (Graph->G[V][W] < 0)
					return false;
				if (dist[V] + Graph->G[V][W] < dist[W]) {
					dist[W] = dist[V] + Graph->G[V][W];
					path[W] = V;
				}
			}
	}
	return true;
}
int main() {
	MGraph Graph = BuildGraph();
	Dijkstra(Graph, dist, path, s);
	printf("%d", dist[t]);
	return 0;
}