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)
typedef std::list AdjVertex;
// Represents adjacency information for all vertices (thus representing
// a complete directed/undirected graph)
typedef std::vector AdjList;

// 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 dist;
std::vector prev;
};

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

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

std::vector dist(num_vertices, infinity); // tentative distances
std::vector prev(num_vertices, undefined_index); // predecessors
std::vector is_visited(num_vertices, false);
std::set 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 s

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++.

StackExchange Code Review Q#41254, answer score: 2