To solve the proposed problem you must use the Dijkstra algorithm for finding the shortest path in a graph. Although the original algorithm finds the shortest path between two given nodes, the requirement here is to find the shortest path between one specified node and all the others in the graph, which is another version of the algorithm.
An efficient way to implement the algorithm is using a priority queue. The pseudocode for the algorithm (see https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) is the following:
function Dijkstra(Graph, source):
dist[source] ← 0 // Initialization
create vertex set Q
for each vertex v in Graph:
if v ≠ source
dist[v] ← INFINITY // Unknown distance from source to v
prev[v] ← UNDEFINED // Predecessor of v
Q.add_with_priority(v, dist[v])
while Q is not empty: // The main loop
u ← Q.extract_min() // Remove and return best vertex
for each neighbor v of u: // only v that is still in Q
alt ← dist[u] + length(u, v)
if alt < dist[v]
dist[v] ← alt
prev[v] ← u
Q.decrease_priority(v, alt)
return dist[], prev[]
To represent the graph we could use the following data structure, which can be used for both directional or unidirectional graphs. The class provides support for adding new vertices and edges, and can return the list of vertices and the neighbors of a specified vertex (that is, both the nodes and the distance to them):
template <typename Vertex = int, typename Weight = double>
class graph
{
public:
typedef Vertex vertex_type;
typedef Weight weight_type;
typedef std::pair<Vertex, Weight> neighbor_type;
typedef std::vector<neighbor_type> neighbor_list_type;
public:
void add_edge(Vertex const source, Vertex const target,
Weight const weight, bool const bidirectional = true)
{
adjacency_list[source].push_back(std::make_pair(target, weight));
adjacency_list[target].push_back(std::make_pair(source, weight));
}
size_t vertex_count() const { return adjacency_list.size(); }
std::vector<Vertex> verteces() const
{
std::vector<Vertex> keys;
for (auto const & kvp : adjacency_list)
keys.push_back(kvp.first);
return keys;
}
neighbor_list_type const & neighbors(Vertex const & v) const
{
auto pos = adjacency_list.find(v);
if (pos == adjacency_list.end())
throw std::runtime_error("vertex not found");
return pos->second;
}
constexpr static Weight Infinity =
std::numeric_limits<Weight>::infinity();
private:
std::map<vertex_type, neighbor_list_type> adjacency_list;
};
The implementation of the shortest path algorithm as described in the preceding pseudocode could look like the following. An std::set (that is, a self-balancing binary search tree) is used instead of the priority queue. std::set has the same 
complexity for adding and removing the top element as a binary heap (used for a priority queue). On the other hand, std::set also allows finding and removing any other element in 
, which is helpful in order to implement the decrease-key step in logarithmic time by removing and inserting again:
template <typename Vertex, typename Weight>
void shortest_path(
graph<Vertex, Weight> const & g,
Vertex const source,
std::map<Vertex, Weight>& min_distance,
std::map<Vertex, Vertex>& previous)
{
auto const n = g.vertex_count();
auto const verteces = g.verteces();
min_distance.clear();
for (auto const & v : verteces)
min_distance[v] = graph<Vertex, Weight>::Infinity;
min_distance[source] = 0;
previous.clear();
std::set<std::pair<Weight, Vertex> > vertex_queue;
vertex_queue.insert(std::make_pair(min_distance[source], source));
while (!vertex_queue.empty())
{
auto dist = vertex_queue.begin()->first;
auto u = vertex_queue.begin()->second;
vertex_queue.erase(std::begin(vertex_queue));
auto const & neighbors = g.neighbors(u);
for (auto const & neighbor : neighbors)
{
auto v = neighbor.first;
auto w = neighbor.second;
auto dist_via_u = dist + w;
if (dist_via_u < min_distance[v])
{
vertex_queue.erase(std::make_pair(min_distance[v], v));
min_distance[v] = dist_via_u;
previous[v] = u;
vertex_queue.insert(std::make_pair(min_distance[v], v));
}
}
}
}
The following helper functions print the results in the specified format:
template <typename Vertex>
void build_path(
std::map<Vertex, Vertex> const & prev, Vertex const v,
std::vector<Vertex> & result)
{
result.push_back(v);
auto pos = prev.find(v);
if (pos == std::end(prev)) return;
build_path(prev, pos->second, result);
}
template <typename Vertex>
std::vector<Vertex> build_path(std::map<Vertex, Vertex> const & prev,
Vertex const v)
{
std::vector<Vertex> result;
build_path(prev, v, result);
std::reverse(std::begin(result), std::end(result));
return result;
}
template <typename Vertex>
void print_path(std::vector<Vertex> const & path)
{
for (size_t i = 0; i < path.size(); ++i)
{
std::cout << path[i];
if (i < path.size() - 1) std::cout << " -> ";
}
}
The following program solves the given task:
int main()
{
graph<char, double> g;
g.add_edge('A', 'B', 7);
g.add_edge('A', 'C', 9);
g.add_edge('A', 'F', 14);
g.add_edge('B', 'C', 10);
g.add_edge('B', 'D', 15);
g.add_edge('C', 'D', 11);
g.add_edge('C', 'F', 2);
g.add_edge('D', 'E', 6);
g.add_edge('E', 'F', 9);
char source = 'A';
std::map<char, double> min_distance;
std::map<char, char> previous;
shortest_path(g, source, min_distance, previous);
for (auto const & kvp : min_distance)
{
std::cout << source << " -> " << kvp.first << " : "
<< kvp.second << '\t';
print_path(build_path(previous, kvp.first));
std::cout << std::endl;
}
}