Dijkstra's Shortest-Distance Algorithm Help

[natekelsey]

I'm having a hard time trying to understand/visualize Step 3a of the pseudocode given to me by my textbook. This is what I have so far for my function. My set class is my own implemented linked list.

ok, here's the pseudocode straight from the book:

input. a directed graph with positive, integer edge weights and n vertices. one of the vertices, called start, is specified as the start vertex.

output. a list of the shortest distances from the start vertex to every other vertex in the graph.

the algorithm uses an array of n integers (called distance) and a set of vertices (called allowed_vertices). the variables v, allowed_size, and sum are local integer variables. there is some special value (-1) that we can place in the distance array to indicate an infinite distane (which means there is no path).

Step 1. initialize the distance array to contain all -1, except distance[start], which is set to zero.

Step 2. initialize the set of allowed vertices to be the empty set.

Step 3. Compute the complete distance array:

Code:

for (allowed_size = 1; allowed_size < n; ++allowed_size)
{
     // at this point, allowed_vertices contains allowed_size - 1 vertices, which are the 
     // allowed_size - 1 closest vertices to the start vertex.  Also, for each vertex v, distance[v] 
     // is the shortest distance from the start vertex to vertex v, provided that we are 
     // considering only permitted paths (i.e., paths where each vertex except the final vertex 
     // must be in allowed_vertices). 

Step 3a. Let next be the closest vertex to the start vertex, which is not yet in the set of allowed vertices (if several vertices are equally close, then you may choose next to be any of them).
Step 3b. Add the vertex next to the set allowed_vertices.
Step 3c. Revise the distance array so that the new vertex (next) may appear on permitted paths:
Code:

for (v = 0;v <  n; ++v)
     {
          if ((v is not an allowed vertex) and (there is an edge from next to v))
          {
               sum = distance[next] + (weight of the edge from next to v);
               if (sum < distance[v])
                    distance[v] = sum;
          }
      }
}

Step 4. Output the values in the distance array. (Each distance[v] is the shortest distance from the start vertex to vertex v.)

This is what I have deciphered so far.

void Graph1::dijkstra(int source)
{
	int distance[MAX_SIZE];
	int i, j, k, l, sum, nextV;
	// Step 1. Initialize the distance array to contain all INFINITY,
	// except distance[source], which is set to 0;
	for (i = 0; i < size(); i++)
		distance[i] = INFINITY; // Using preset value for INFINITY
	distance[source] = 0;

	// Step 2. Initialize the set of used vertices to be the empty set
	Set1 usedVertices;

	// Step 3. Compute the distance array
	for (j = 1; j < usedVertex - 1; ++j)
	{
                // HERE
		// 3a. Let nextV be the closest vertex to the start vertex
		// that is not yet in the set of usedVertices.

		// 3b. Add the vertex nextV to the set usedVertices
		usedVertices.insert(nextV);
		// 3c. Revise distance array so that the new
		// vertex(next) may appear on permitted paths(Set1 Class)	
		for (k = 0; k < size(); ++k)
		{
			if ((!usedVertices.isIn(k)) && isEdge(nextV, k))
			{
				sum = distance[nextV] + (wEdges[nextV][k]);
				if (sum < distance[k])
					distance[k] = sum;
			}
		}
	}

	for (i = 0; i < size(); i++)
	{
		if (distance[i] != INFINITY)
			cout << i << " " << distance[i] << endl;

	}
}

Could someone help me understand how I go about implementing Step3a. So far it's the only one I'm stumped with.

[Smac89]

You are missing something important in your implementation. Where do you store the unvisited vertices which are on the path to the source? These vertices are the ones connected to some vertex which is already in the usedSet.