Problem w/ Dijkstra’s Algorithm(reading input and building Adjacency lists)

Discussion in 'OT Technology' started by SPACECATAZ, Feb 19, 2009.

  1. SPACECATAZ

    SPACECATAZ New Member

    Joined:
    Dec 22, 2006
    Messages:
    2,502
    Likes Received:
    0
    Hello, I'm trying to write a program to implement Dijkstra's algorithm, but I have ran into a snag when I'm trying to read in the input for the vertexes and the weight for each edge and storing them into adjacency lists.

    From my understanding, the input will go something like this.

    5
    1 2 9.0
    1 3 12.0
    2 4 18.0
    2 3 6.0
    2 5 20.0
    3 5 15.0
    0

    That says that there are five vertices. There is an edge from
    vertex 1 to vertex 2, with weight 9.0, an edge from vertex 1 to vertex 3
    with weight 12.0, etc. The start vertex s
    is 1, and the end vertex t is 5.

    This is what one of the graphs might look like for a visual reference, but this is not what I'm trying to output in the end.

    [​IMG]

    This is would be an example of the end input.

    There are 5 vertices.
    The edges are as follows.

    (1,3) weight 12.000
    (1,2) weight 9.000
    (2,5) weight 20.000
    (2,3) weight 6.000
    (2,4) weight 18.000
    (3,5) weight 15.000

    The shortest path from 1 to 5 has length 27.000 and is
    1 -> 3 -> 5

    This is the code I have so far.

    Code:
    
    #include <iostream>
    #include <cstdio>
    using namespace std;
    enum StatusType {Done, Pending, Peripheral};
    
    
    struct Adjacent
    {
      int vertex;  
      double weight; //weight of vertex
      Adjacent* next;
    
      Adjacent(int v, double w, Adjacent* n)
      {
        vertex = v;
        weight = w;
        next = n;
      }
    };
    
    struct Vertex
    {
        StatusType status; //current status of a vertex
        int nextVertex;
        double currentDV; //current distance value
            Adjacent* adj; 
    };
      
    
     struct Graph
     {
       int numVertices; //number of vertices 
       int numEdges;
       Vertex* info;
    
       Graph(int nv)
       {
         numVertices = nv;
         info = new Vertex[nv+1];
       }
     };
    
    /****************************************************************
     *                      readGraph                             *
     ****************************************************************
     * readGraph reads information about a weighted graph from the  *
     * standard input.                                              *
     ****************************************************************/
     void readGraph(Graph& g)
     {
        cin >> n;
        Graph gg(n);
        g = gg;
        for(int i=1; i<= g.numVertices; i++)
        { 
            g.info[i].adj = NULL;
        }
        
        for(int k=
        
            //cin >> vertex1  >> vertex2 >> weight;
            g.info[n].adj = new Adjacent(vertex1, vertex2, weight); //allocate new memory for vertex
            g.info[n].adj = new Adjacent(vertex2, vertex1, weight); //allocate new memory for vertex
            }
            
        
    /****************************************************************
     *                     printGraph                                *
     ****************************************************************
     * printGraph will print a description of the graph, followed   *
     *  by the shortest path from s to t and the distance from s to *
     *  t via that path, on the standard output.                    *
     ****************************************************************/
        
     void printGraph()
     {
        
    }
     
    int main()
    {
      Graph g;
      readGraph(g);
      
    
    }
    


    The adjacent structure is what I built to handle the lists and initialize them correctly, but I have to read in the put like above and keep reading it until the input is zero. This is when it will stop storing the adjacency list. It will then take in the last two inputs which signifies where you're trying to go, like above in the input example where it says "1 to 5". That means you're trying to find the short distance from 1 to 5. I figured I could use a run until a zero pops up, but what about when I need to take in 1 to 5 as well?

    As the for loop is taking in the information, it's supposed to be storing it in the adjacency lists.

    My assignment says," Read a graph, in the format described under the requirements. Build up the adjacency lists as you read the graph. When you read an edge from u to v, put it into both the adjacency list of u and the adjacency list of v. That is, indicate that u is adjacent to v and v is adjacent to u. "

    I figure I could use a while loop as well, but I'm not sure how to initialize the input, but I have constructors that take of that for me. I'm just not sure how to tackle that.

    Thanks.

     

Share This Page