I am having trouble following this code using Dijkstra\'s algorithm. Can anyone

Question

I am having trouble following this code using Dijkstra's algorithm. Can anyone provide comments of what is actually going on. Thanks

#include <iostream>

#include <vector>

#include <string>

#include <list>

#include <limits> // for numeric_limits

#include <set>

#include <utility> // for pair

#include <algorithm>

#include <iterator>

typedef int vertex_t;

typedef double weight_t;

const weight_t max_weight = std::numeric_limits<double>::infinity();

struct neighbor { vertex_t target; weight_t weight; neighbor(vertex_t arg_target, weight_t arg_weight) : target(arg_target), weight(arg_weight) { } };

typedef std::vector<std::vector<neighbor> > adjacency_list_t;

void DijkstraComputePaths(vertex_t source, const adjacency_list_t &adjacency_list, std::vector<weight_t> &min_distance, std::vector<vertex_t> &previous) {

int n = adjacency_list.size();

min_distance.clear();

min_distance.resize(n, max_weight);

min_distance[source] = 0; previous.clear();

previous.resize(n, -1);

std::set<std::pair<weight_t, vertex_t> > vertex_queue; vertex_queue.insert(std::make_pair(min_distance[source], source));

while (!vertex_queue.empty())

{ weight_t dist = vertex_queue.begin()->first;

vertex_t u = vertex_queue.begin()->second;

vertex_queue.erase(vertex_queue.begin());

// Visit each edge exiting u

const std::vector<neighbor> &neighbors = adjacency_list[u];

for (std::vector<neighbor>::const_iterator neighbor_iter = neighbors.begin();

neighbor_iter != neighbors.end(); neighbor_iter++) { vertex_t v = neighbor_iter->target; weight_t weight = neighbor_iter->weight; weight_t distance_through_u = dist + weight;

if (distance_through_u < min_distance[v]) { vertex_queue.erase(std::make_pair(min_distance[v], v));

min_distance[v] = distance_through_u;

previous[v] = u; vertex_queue.insert(std::make_pair(min_distance[v], v)); } } } }

std::list<vertex_t> DijkstraGetShortestPathTo( vertex_t vertex, const std::vector<vertex_t> &previous) { std::list<vertex_t> path;

for ( ; vertex != -1; vertex = previous[vertex]) path.push_front(vertex); return path; }

int main() { // remember to insert edges both ways for an undirected graph adjacency_list_t adjacency_list(6);

// 0 = a

adjacency_list[0].push_back(neighbor(1, 7));

adjacency_list[0].push_back(neighbor(2, 9));

adjacency_list[0].push_back(neighbor(5, 14));

// 1 = b

adjacency_list[1].push_back(neighbor(0, 7));

adjacency_list[1].push_back(neighbor(2, 10));

adjacency_list[1].push_back(neighbor(3, 15));

// 2 = c

adjacency_list[2].push_back(neighbor(0, 9));

adjacency_list[2].push_back(neighbor(1, 10));

adjacency_list[2].push_back(neighbor(3, 11));

adjacency_list[2].push_back(neighbor(5, 2));

// 3 = d

adjacency_list[3].push_back(neighbor(1, 15));

adjacency_list[3].push_back(neighbor(2, 11));

adjacency_list[3].push_back(neighbor(4, 6));

// 4 = e

adjacency_list[4].push_back(neighbor(3, 6));

adjacency_list[4].push_back(neighbor(5, 9));

// 5 = f

adjacency_list[5].push_back(neighbor(0, 14));

adjacency_list[5].push_back(neighbor(2, 2));

adjacency_list[5].push_back(neighbor(4, 9));

std::vector<weight_t> min_distance; std::vector<vertex_t> previous;

DijkstraComputePaths(0, adjacency_list, min_distance, previous);

std::cout << "Distance from 0 to 4: " << min_distance[4] << std::endl;

std::list<vertex_t> path = DijkstraGetShortestPathTo(4, previous);

std::cout << "Path : "; std::copy(path.begin(), path.end(), std::ostream_iterator<vertex_t>(std::cout, " ")); std::cout << std::endl; return 0; }

Explanation / Answer

in the main function function adjacency_list is not declaired in the main function.

and the type of this will be the same as the push_back function.

line no 38 make correction only.....

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.