Random map generator (adjacency matrix) and shortest path algorithm for grass realization

I haven't realized something in the data structure algorithm. The day before yesterday, I wrote this random map to generate functions and realize the shortest path algorithm Dijkstra. I will miss the university life that is already far away! To pay attention to the generation of the graph 1) There is no self-ride, that is The matrix is ​​to generate the diagonal symmetrical, which can be generated by generating a top (below) triangular array. Compare messy, some security judgment code can put it in a function to make the program make it easier. / ******************************************* * File: Dijkstra . CPP * * * AUTHOR: LUTE * * DATE: JAN, 23nd, 2005 * * Desc: We Well Provide a implient * * of random graph generator and * * the dijkstra algorithm * ************ ******************************* /

#include #include #include // for function memset () #include // for function time (), as random seed. IF You are using //vs6.0, replace it as #include

#define infinite 1000000 #define allknown -2 #define min (a, b) (A> B? B: a)

// definition of the node of the graph struct node {int id; // The id of the node int data; // The data store in node bool known; // is known? reserve for some algorithm};

Typedef struct node node;

// definition of the Graph structure struct graph {int num; // the number of node Node * gnode; // pointer to the graph node list int * ajcent; // pointer to the ajacent matrix, and we will store n * n // edges'infomation in one-dimension array};

Typedef struct graph graph

Graph * GenRandGraph (int nodenum) {int i; int adjcentnum = nodenum * nodenum; // initialize the graph Graph * graph = NULL; graph = (Graph *) malloc (sizeof (Graph)); memset (graph, 0, sizeof (Graph); if (! Graph) {Printf ("Genrandgraph 1: NOT ENOUGH MEMORY TO Allocate! / N"); return null;} graph-> num = nodenum; graph-> gnode = (node ​​*) malloc Sizeof (node) * nodenum); graph-> ajcent = (int *) malloc (sizeof (int) * adjgentnum); if (! graph-> gnode) {printf ("Genrandgraph 2: Not Enough Memory To Allocate! / N "); Free (graph); // before return we must to set what we have free! Graph = null; return null;} if (! Graph-> ajcent) {Printf (" Genrandgraph 3: Not Enough Memory to Allocate! / N "); free (graph-> gnode); graph-> gnode = null; free (graph); graph = null; return null;} // random seed SR AND (Time (NULL)); for (i = 0; i gnode [i] .id = i; graph-> gnode [i] .data = rand ()% 10; GRAPH -> gnode [i] .Known = false;} for (i = 0; i ajcent [i] = (RAND ()% 2) * (Rand ()% 10); //// And the graph shull not contact the self-loop struct so ... for (i = 0; i ajcent [i * nodenum i] = 0; Return graph;}

// free all momory allocated for the graph, the void deletegraph (graph * graph) {if (! Graph) return; if (graph-> gnode) {free (graph-> gnode); graph-> gnode = null;} IF (graph-> ajcent); graph-> ajcent = null;} free (graph); graph = null;} //printing the content of the nodes and the adjacnt Matrix of the graph void Printgraph (graph * graph) {INT I, Adjacentnum; if (! Graph) {printf ("Printgraph 1: graph is null / n"); return;} // print info of nodes / vertice if (graph-> gnode) {Printf ("graph node:"); for (i = 0; i Num; i ) Printf ("% D-% D", graph-> gnode [i] .id, graph-> gnode [ I] .data);} // print adjacent matrix if (graph-> ajcent) {adjgentnum = graph-> num * graph-> num; printf ("/ n / najacnt matrix: / n"); for (i = 0; i num == 0) Printf ("/ n"); Printf ("% D", graph-> ajcent [i]);} printf ("/ n");}}

// set the weight from Vertex I to Vertex J Bool SetedgeWeight (INT I, INT J, INT Weight, graph * graph) {// graph is null? If (! Graph) {printf ("SteEDGEWEight 1: graph is null! / N "); RETURN FALSE;} // graph Have Been INITIALIZED? IF (graph-> Num == 0 ||! graph-> gnode ||! graph-> ajcent) {printf (" STEDGEWEIGHT 2: graph is not Initialized! / n "); RETURN FALSE;} // Parament Invaild? and you notice That i == J Is An Condition Inix (...) // Since Our Graph Should Not Contian Self-Loop IF (i <0 || j <0 || i> = graph-> NUM || j> = graph-> num || i == j) {printf ("setEdgeWeight 3: Invalid Verter Number! / n"); Return False;} Graph-> ajcent [i * graph-> Num j] = weight; return true;} // Get Weight from the Edge (IJ) INT getEtedGeweight (int I, int J, graph * graph) {// is graph null ? If (! Graph) {printf ("getEdgeWeight 1: graph is null / n"); return -1;} // Have GRAPH BEEN INITIALIZED? IF (graph-> Num == 0 ||! graph-> gnode ||! graph-> ajcent) {printf ("getEdgeWeight 2: graph is not initf! / n"); Return -1;} // is the parameters invaild? IF (i <0 || j <0 || i> = graph-> num || j> = graph-> num) {Printf ("getEdgeWeight 3: Invalid parameters! / N") Return -1;} return graph-> ajcent [i * graph-> Num j];}

/ ******* Function Below for dijkstra algorithm ********** /

// HAVE THIS NODE BEEN KNOWN? BOOL IskNown (INT I, Graph * GRAPH) {// is graph null? If (! Graph) {printf ("isknown 1: graph is null / n"); Return -1;} // have graph been initialized? If (graph-> Num == 0 ||! Graph-> gnode ||! Graph-> ajcent) {printf ("isknown 2: graph is not initailized! / N"); return - 1;} // is the parameters invaild? IF (i <0 || i> = graph-> num) {Printf ("isknown 3: invalid parameters! / N"); return -1;} return graph-> gnode [i] .Known;} // set graph node as known bool setknown (INT I, graph * graph) {// is graph null? if (! graph) {printf ("setknown 1: graph is null / n") Return false;} // Have Graph been initialized? IF (graph-> num == 0 ||! Graph-> gnode ||! Graph-> ajcent) {printf ("setknown 2: graph is not initailized! / N "); Return false;} // is the parameters invaild? IF (i <0 || i> = graph-> num) { Printf ("setknown 3: invalid parameters! / N"); return false;} graph-> gnode [i] .Known = true; return true;

// Get a node which is not know and have the minimum path weight Int getminunkown (int * path, graph * graph) {INT i; int min = infinite, minNode = allknown; // is graph null? If (! Graph) {Printf ("getminunkown 1: graph is null / n"); return -1;} // Have graph been initialized? If (graph-> num == 0 ||! Graph-> gnode ||! Graph-> ajcent ) {Printf ("getminunkown 2: graph is not initailized! / N"); return -1;} if (! Path) {printf ("getminnkown 3: path is null / n"); return -1;} for i = 0; i num; i ) IF (! isknown (i, graph) && Path [i]

// Dijkstra Algorithm for Single Node Shortest-Path Finding Bool Dijkstra (INT * PATH = NULL; INT J, TEMP, MinNode = I, K; // Is Graph Null? If (! Graph) {Printf ("Dijkstra 1: graph is NULL / N"); Return False;} // Have GRAPH BEEN INITIAALIZED? IF (graph-> Num == 0 ||! Graph-> gnode ||! Graph-> ajcent) {Printf ("Dijkstra 2: graph is not initailized! / N"); return false;} // is the parameters invaild? IF (i <0 || i> = graph-> num) {Printf ("Dijkstra 3: Invalid parameters! / N "); Return False;} path = (int *) malloc (sizeof (int) * graph-> num); if (! PATH) {Printf (" Dijkstra 4: Not Enough Memory to Allocate! / N "); Return False;} // Initial for (j = 0; j Num; j ) {TEMP = GetGeweight (i, j, graph); if (temp) path [j] = Temp; Else Path [J] = infinite; PATH [I] = 0; setknown (i, graph); for (j = 0; j num; j ) {minNode = getminnkown (path, graph);

IF (MinNode! = Allknown && MinNode! = - 1) {setknown (MinNode, Graph); for (k = 0; k num; k ) {temp = getEtedGeweight (MinNode, K, Graph); if ( Temp! = 0 && Temp! = - 1 && K! = minNode) Path [K] = min (Path [K], Path [MinNode] TEMP);}} }printf ("/ N / NSHORTEST PATH: / N "); For (j = 0; j Num; j ) {if (j% 4 == 0) Printf (" / n "); Printf ("% 3D -% - 3D:% D ", I, J, Path [J]); graph-> gnode [j] .known = false;} printf ("/ n"); return true;} int main () {graph * pgraph = genrandgraph (36); if (! pgraph) {Printf ("Can not generate random graph! / n"); return -1;} Printgraph (PGRAPH);

Dijkstra (10, pgraph); deletegraph (pgraph); system ("pause"); return 0;}