그림 의 Dijkstra 알고리즘

#include 
#include 
#include 

#define MaxSize 10
#define eletype int 
using namespace std;

bool visited[MaxSize];
typedef struct AdjListGraph {
	int adjlist[MaxSize][MaxSize];  //    
	eletype data[MaxSize];
	int vex;  //   
	int edge; //  
};


void Init(AdjListGraph &G) {  //       
	for (int i = 0; i < MaxSize; i++) {
		visited[i] = false;
		for (int j = 0; j < MaxSize; j++) {
			G.adjlist[i][j] = 999;  //     
		}
	}
}

int Location(AdjListGraph &G, eletype c) {  //          
	for (int i = 0; i < G.vex; i++) {
		if (G.data[i] == c) {
			return i;
		}
	}
	return -1;
}

void Create(AdjListGraph &G) {  //   
	cout << "             ：" << endl;
	cin >> G.vex >> G.edge;
	cout << "       ：" << endl;
	for (int i = 0; i < G.vex; i++) {
		cin >> G.data[i];
	}
	eletype a, b;
	int c;
	int m, n;
	cout << "             ：" << endl;
	for (int i = 0; i < G.edge; i++) {
		cin >> a >> b>>c;
		m = Location(G, a);  //     
		n = Location(G, b);

		if (m != -1 && n != -1) {  //     
			G.adjlist[m][n] = c;
		}
	}
}

void Dijkstra(AdjListGraph &G,vector &p, vector &dist,int v) {
	vector vec;
	vec.push_back(v);
	visited[v] = true;  //      
	//   dist
	dist.assign(G.vex, 999);
	p.assign(G.vex, -1);
	dist[v] = 0;  //           0
	for (int i = 0; i < G.vex; i++) {
		if (G.adjlist[v][i] != 999) {
			dist[i] = G.adjlist[v][i];
		}
	}
	int count = G.vex;
	while (count > 1) {
		//  Vj
		int min = 999, tag;
		for (int i = 0; i < vec.size(); i++) {
			for (int j = 0; j < G.vex; j++) {
				if (visited[j] == false && min > G.adjlist[vec[i]][j]) {
					min = G.adjlist[vec[i]][j];  //  
					tag = j;
				}
			}
		}
		vec.push_back(tag); //      
		visited[tag] = true;  //      
							  //    
		for (int i = 0; i < G.vex; i++) {
			if (visited[i] == false && dist[tag] + G.adjlist[tag][i] < dist[i]) {
				dist[i] = dist[tag] + G.adjlist[tag][i];
				p[i] = tag;
			}
		}
		count--;
	}
}

void Path(AdjListGraph &G,vector &p,int begin,int end) {  //    
	stack s;
	s.push(G.data[end]);
	while (p[end] != -1) {
		s.push(G.data[p[end]]);
		end = p[end];
	}
	s.push(G.data[begin]);
	//    
	while (!s.empty()) {
		cout << s.top() << " ";
		s.pop();
	}

}


int main() {
	AdjListGraph G;
	vector p;
	vector dist;
	Init(G);
	Create(G);  //   
	Dijkstra(G,p,dist,0);
	Path(G,p,0,2);
	system("pause");
	return 0;
}

/*
5 10
1 2 3 4 5
1 2 10
1 5 5
2 5 2
5 2 3
2 3 1
5 3 9
5 4 2
4 1 7
3 4 4
4 3 6

*/