// From the software distribution accompanying the textbook // "A Practical Introduction to Data Structures and Algorithm Analysis, // Third Edition (C++)" by Clifford A. Shaffer. // Source code Copyright (C) 2007-2011 by Clifford A. Shaffer. // Test program for Dijkstra's single-source shortest paths algorithm // Version 1: Use a simple scan of the distance matrix to find the next // closest node. // Use any of the files in this directory with a .gph extension. // This version is for the Adjancency Matrix representation #include "book.h" #include "grmat.h" int minVertex(Graph*, int*); // Compute shortest path distances from "s". // Return these distances in "D". void Dijkstra(Graph* G, int* D, int s) { int i, v, w; for (i=0; in(); i++) { // Process the vertices v = minVertex(G, D); if (D[v] == INFINITY) return; // Unreachable vertices G->setMark(v, VISITED); for (w=G->first(v); wn(); w = G->next(v,w)) if (D[w] > (D[v] + G->weight(v, w))) D[w] = D[v] + G->weight(v, w); } } int minVertex(Graph* G, int* D) { // Find min cost vertex int i, v = -1; // Initialize v to some unvisited vertex for (i=0; in(); i++) if (G->getMark(i) == UNVISITED) { v = i; break; } for (i++; in(); i++) // Now find smallest D value if ((G->getMark(i) == UNVISITED) && (D[i] < D[v])) v = i; return v; } // Test Dijkstra's algorithm: // Version for Adjancency Matrix representation int main(int argc, char** argv) { Graph* G; FILE *fid; if (argc != 2) { cout << "Usage: grdijk1m \n"; exit(-1); } if ((fid = fopen(argv[1], "rt")) == NULL) { cout << "Unable to open file |" << argv[1] << "|\n"; exit(-1); } G = createGraph(fid); if (G == NULL) { cout << "Unable to create graph\n"; exit(-1); } int D[G->n()]; for (int i=0; in(); i++) // Initialize D[i] = INFINITY; D[0] = 0; Dijkstra(G, D, 0); for(int k=0; kn(); k++) cout << D[k] << " "; cout << endl; return 0; }