# Help!!! Shortest path graph

• 02-28-2002
hansy32
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);
}
}
}
• 02-28-2002
Salem
Looks OK so far, what's the problem?

If you're looking for algorithm help - try a book or a web search.
• 02-28-2002
Unregistered
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.
• 03-01-2002
hansy32
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???
• 03-01-2002
Salem
Not until you've shown some effort in solving it yourself

www.code-spoonfeeders.com
• 03-01-2002
Unregistered
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.