Dijkstra Shortest Path help (almost complete)

[Reaga]

I'm one piece of the algorithm away from finishing an assignment, but for the life of me I cannot figure out how to implement this pseudo code line.

A weighted graph is being defined by a text file. In the text file, the top line is the number of vertices, and the rest of the lines are 3 numbers defining edges: vertex 1, vertex 2, and cost (parameters for each edge).

Example:

7
0 1 2
0 3 1
1 3 3
1 4 10
2 0 4
2 5 5
3 2 2
3 4 2
3 5 8
3 6 4
4 6 6
6 5 1

Given the graph class definition here:

class Graph
{
  struct Edge
  {
    int dest;    // destination vertex number
    int cost;    // edge weight
    Edge *next;
  };

  struct Vertex
  {
    Edge *adj;
    bool known;
    int  dist;
    int  path;
  };

  vector<Vertex *> vertices;
  vector<int>      PQ;
  int              PQsize;

  void PQinsert (int v);
  int  PQdeleteMin ();

public:
  Graph () { PQsize=0; }
  int  numVertices ()  { return vertices.size(); }
  int  dist (int dest) { return vertices[dest]->dist; }
  void readFile (char *name);
  void dijkstra  (int start);
  void printPath (int dest);

I need to be able to determine and cycle through all vertices adjacent to a starting vertex.

I imagine that would involve determining how many edges are associated with the starting vertex and going through each vertex on the other end of the edge, but I cannot for the life of me figure out how to determine and cycle through all edges connected to a vertex when each Vertex only has a single Edge parameter. This would be easy if he had implemented an adjacency list for each vertex, cycling through such a list would be easy, but he chose not to.

[ne555]

> the top line is the number of edges, and the rest of the lines are (...) (parameters for each edge).
¿so why your example input has 13 lines instead of 8?


> This would be easy if he had implemented an adjacency list for each vertex
maybe that's exactly what's doing.
I don't realize another meaning for `next' edge, and `vertex::adj' edge.

[Reaga]

My appologies, I meant the top number is the number of vertices.

As for the other comment, it just seems to me like each vertex has been coded to allow only one "vertex::adj' edge, unless I'm misreading the code.

[ne555]

vertex::adj would point to the starting cell of the adjacency list.
and you would use the `next' field to traverse it.

that's just an assumption and don't understand why don't simply use std::{forward_,}list

[Reaga]

I'm afraid I don't follow. Maybe I'm interpreting wrong, but

Edge *adj; seems to define a pointer to one adjacent edge. I don't see a list being created here. If I'm wrong, maybe you could explain why/how it would create a list w/ that declaration?

as for std::{forward_,}list, I probably would if we were allowed to change anything but the dijkstra method, which he has specifically forbidden

[ne555]

class node_list{
public:
   node_list *next;
};

class list{
public:
   node_list *head;
};

int main(){
   list l;
   l.head = NULL; //empty list
   l.head = new node_list; //inserting one element
   l.head->next = new node_list; //another element
   l.head->next->next = new node_list; //yet another element
   l.head->next->next->next = NULL;
}

replace list with Vertex, and node_list with Edge.


It may be using another representation, ¿so why don't you go and ask instead of playing a guessing game?