#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; }