# Thread: Help!!! Shortest path graph

1. ## Help!!! Shortest path graph

Is there anybody out there that could help me with the following problem???
http://ice.prohosting.com/jbratset/cgi-bin/Project.doc

Here is my code so far:

#include <stdio.h>

#define GRAPHSIZE 10
#define MAXNEIGHBOURS 4
struct Graph{
int degree;
int Neighbors[MAXNEIGHBOURS];
int Neigh_Weight[MAXNEIGHBOURS];
};

struct Graph GraphArray[GRAPHSIZE];
main()
{
int vtx, vtx_degree, neighbor, neighbour_id, weight;

for ( vtx = 0; vtx < GRAPHSIZE; vtx++){

printf(" Total Neighbors for vertex Nr: %d ?\n",vtx);
scanf("%d", &vtx_degree);
GraphArray[vtx].degree = vtx_degree;
for (neighbor = 0; neighbor < vtx_degree; neighbor++){
printf(" Give the id of neighbor Nr: %d\n", neighbor + 1);
scanf("%d", &neighbour_id);
GraphArray[vtx].Neighbors[neighbor] = neighbour_id;
printf(" Weight for the edge <%d %d>\n", vtx, neighbour_id);
scanf ("%d", &weight);
GraphArray[vtx].Neigh_Weight[neighbor] = weight;
}

}

for (vtx = 0; vtx < GRAPHSIZE; vtx++){
vtx_degree = GraphArray[vtx].degree;
printf(" vtx = %d total_neighbors = %d\n", vtx, vtx_degree);
for ( neighbor = 0; neighbor < vtx_degree; neighbor++){
neighbour_id = GraphArray[vtx].Neighbors[neighbor];
weight = GraphArray[vtx].Neigh_Weight[neighbor];
printf(" vtx =%d neighbour_id= %d weight=%d\n", vtx, neighbour_id, weight);
}
}
}

2. Looks OK so far, what's the problem?

If you're looking for algorithm help - try a book or a web search.

3. i agree with Salem, the code looks right.

Look in a data structrues text.

Also, the problem sound like a MST problem.

If so, look up Prim or Kruskal's algorithms

Mr. C.

4. Thanks for the tip about using the Prim or Kruskal's algorithms. I can see that this algorithm will solve my problem. But is there anybody out there that know how to implement this algorithm???

5. Not until you've shown some effort in solving it yourself

www.code-spoonfeeders.com

6. I agree with salem, try your self first.

Hint: Look up the algorithms in a text book or on the net!

The code is straightforward- once you understand it.

Mr. C.