# Dijkstra's and Prim's algorithms: correctness/efficiency

This is in preparation for a competition that only allows C++03.

// Neighbor index plus weight of edge connecting this vertex with neighbor
struct NeighborWeight
{
Index neighbor;
Distance weight;
};
// Represents adjacency information for a single vertex (contains all
// neighbors and weights of edges connecting them)
// Represents adjacency information for all vertices (thus representing
// a complete directed/undirected graph)

// Dijkstra's algorithm: computes SHORTEST PATH to all vertices from a starting
// vertex for a DIRECTED/UNDIRECTED graph with NONNEGATIVE edge weights.
// result.dist[v] = shortest distance from source to v.
// result.prev[v] = predecessor of v in shortest path from source to v.
// If v is not connected to start_vertex, dist[v] = max value of Distance, and
// prev[v] = -1.
// If v = start_vertex, prev[v] = -1.

// Prim's algorithm (call with do_prim = true): computes MINIMUM SPANNING TREE
// starting from a seed vertex for an UNDIRECTED graph with ANY edge weights.
// result.dist[v] should be ignored.
// result.prev[v] = parent of v in minimal spanning tree.
// If v is not connected to start_vertex, prev[v] = -1.
// If v = start_vertex, prev[v] = -1;

struct DijkstraResult
{
std::vector<Distance> dist;
std::vector<Index> prev;
};

DijkstraResult dijkstra(AdjList al, Index start_vertex, bool do_prim = false)
{
typedef std::pair<Distance, Index> DistAndIndex;

const Distance infinity = std::numeric_limits<Distance>::max();
const Index undefined_index = -1;
const Index num_vertices = al.size();

std::vector<Distance> dist(num_vertices, infinity); // tentative distances
std::vector<Index> prev(num_vertices, undefined_index); // predecessors
std::vector<uint8_t> is_visited(num_vertices, false);
std::set<DistAndIndex> unvisited_queue;

dist[start_vertex] = 0;

// Populate unvisited_queue in order with (Distance, Index) pairs
unvisited_queue.insert(std::make_pair(0, start_vertex));
for (Index v = 0; v < num_vertices; ++v)
if (v != start_vertex)
unvisited_queue.insert(unvisited_queue.end(),
std::make_pair(infinity, v));

while (!unvisited_queue.empty())
{
// u = index of unvisited vertex with least distance
Index u = unvisited_queue.begin()->second;
// If this least distance is infinity, break (no more connected verts)
if (unvisited_queue.begin()->first == infinity) break;
// Visit this vertex
unvisited_queue.erase(unvisited_queue.begin());
is_visited[u] = true;
// In Prim's, distances are computed from the MST. Adding a vertex
// to the MST makes the distance 0.
if (do_prim) dist[u] = 0;
// vert = vertex corresponding to u
// Iterate through neighbors of u
for (AdjVertex::iterator it = vert.begin(); it != vert.end(); ++it)
{
// v = it->neighbor is the index of the neighbor; it->weight is the
// edge weight between u and v
Index v = it->neighbor;
// Skip if v is visited
if (is_visited[v]) continue;
// Now compute new dist for v
Distance alt = dist[u] + it->weight;
// And compare with previous
if (alt < dist[v])
{
unvisited_queue.erase(std::make_pair(dist[v], v));
unvisited_queue.insert(std::make_pair(alt, v));
dist[v] = alt;
prev[v] = u;
}
}
}

DijkstraResult res = { dist, prev };
return res;
}


There's another set of typedefs and functions that duplicates a list of undirected edges into an AdjList structure.

• competition that only allows C++03 you should have entered this before 2011. By now the language standard has moved on. – Walter Feb 9 '14 at 18:19

I'll address some minor things (unrelated to efficiency, at least):

• The comments describing the algorithm could be at the very top so that the code in between isn't missed. Any comments describing the functions or the typedefs can stay above them.

• These structs are in global scope, so they should be contained by something (such as a function) to put them into local scope, preventing unknown modifications.

For instance, DijkstraResult could probably be defined in the calling code, which I assume is main() (not shown here). Wherever the result of dijkstra() is received, that struct should be contained there. This will also help with keeping code lower in scope, which eases maintenance and prevents bugs associated with this.

• If you still want a typedef for the std::pair, at least consider a less-obvious (and possibly more accurate) name. The name DistAndIndex can still be read from the std::pair, so it doesn't help much. It also doesn't save very many keystrokes, if that's even a concern.

• The name infinity doesn't make sense here as you're not assigning it to anything considered infinite (it's also not a number, but a concept). It is assigned to a max value, which is finite, also according to the documentation.

Bearing that in mind, a more appropriate name may be something like maxDistance.

• Curly braces should be used here:

for (Index v = 0; v < num_vertices; ++v)
if (v != start_vertex)
unvisited_queue.insert(unvisited_queue.end(),
std::make_pair(infinity, v));


From a readability standpoint, it's not entirely clear what is contained in what. It can also hurt maintainability as adding or removing code from here can break something.

Regarding the code within the if block, the second line should be indented so that it is not read as a separate statement.

for (Index v = 0; v < num_vertices; ++v)
{
if (v != start_vertex)
{
unvisited_queue.insert(unvisited_queue.end(),
std::make_pair(infinity, v));
}
}

• uint8_t should be std::uint8_t in C++.