程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> C++實現Dijkstra算法

C++實現Dijkstra算法

編輯：C++入門知識

C++實現Dijkstra算法

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;

const int INF = INT_MAX;

struct Node{
	int pre;
	int dist;
	bool visited;
	Node() : pre(-1), dist(INF), visited(false) {}
};


void dispT(vector & T) {
	for (int i = 0; i < T.size(); ++i) {
		cout << "Num: " << i << "  Dist: " 
			<< T[i].dist << "  Pre: " << T[i].pre << endl;
	}
	return;
}

int Extract_Min(vector & T) {
	int mark = -1;
	for (int i = 0; i < T.size(); ++i) {
		if (!T[i].visited) {
			if (mark == -1)
				mark = i;
			else if (T[i].dist < T[mark].dist)
				mark = i;
		}
	}
	return mark;
}

void Dijkstra(vector > & G, size_t src)
{
	//check validity.
	if (src >= G.size()) 
		return;

	vector T(G.size());
	T[src].dist = 0;

	for (int i = 0; i < G.size(); ++i) {
		int tag = Extract_Min(T);
		assert(tag != -1);	//debug.

		T[tag].visited = true;
		//update the weights of edges,taversing in the same manner as BFS.
		for (int j = 0; j < G.size(); ++j) {
			if (!T[j].visited && G[tag][j] != INF 
				&& T[j].dist > G[tag][j] + T[tag].dist) {
				T[j].dist = G[tag][j] + T[tag].dist;
				T[j].pre = tag;
			}
		}
	}

	//output.
	dispT(T);
}

int main(void)
{
	cout << "Dijkstra Algorithm for Directed Graph:" << endl;

	while (true) {
		int N;
		cout << "Number of Nodes: ";
		cin >> N;
		vector >
			G(N, vector(N, INF));
		for (int i = 0; i < N; ++i)
			G[i][i] = 0;

		int M;
		cout << "Number of Edges: ";
		cin >> M;
		for (int i = 0; i < M; ++i) {
			int s, e;
			cin >> s >> e;
			cin >> G[s][e];
		}

		for (int src = 0; src < N; ++src) {
			cout << "From " << src << " :" << endl;
			Dijkstra(G, src);
			system("pause");
		}
	}
	system("pause");
	return 0;
}