Dijkstra's and Prim's algorithms: correctness/efficiency
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 &lt; 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 &lt; 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++.