Thread: Help!!! Shortest path graph

  1. #1
    Registered User
    Join Date
    Feb 2002
    Posts
    3

    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);
    }
    }
    }
    Last edited by hansy32; 02-28-2002 at 03:29 AM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Looks OK so far, what's the problem?

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

  3. #3
    Unregistered
    Guest

    Lightbulb

    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. #4
    Registered User
    Join Date
    Feb 2002
    Posts
    3
    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. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Not until you've shown some effort in solving it yourself

    www.code-spoonfeeders.com

  6. #6
    Unregistered
    Guest
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Shortest Path Maze Solver (Breadth Search Help)
    By Raskalnikov in forum C Programming
    Replies: 5
    Last Post: 04-07-2009, 07:41 PM
  2. error help making no sense
    By tunerfreak in forum C++ Programming
    Replies: 5
    Last Post: 04-17-2007, 07:55 PM
  3. Shortest path problem
    By Digitalxero in forum C++ Programming
    Replies: 0
    Last Post: 10-25-2005, 05:32 PM
  4. graph optimum path
    By Mist in forum C Programming
    Replies: 1
    Last Post: 03-06-2005, 04:39 PM
  5. determining a path through the graph
    By Mist in forum C Programming
    Replies: 2
    Last Post: 02-27-2005, 12:21 PM