i have a shortest path algorithm from my c++ book, but there are some problems with my implementation.
for one thing, i don't see how it will expand the search to further vertices after it gets the set of "neighbors" from the source vertex. (i believe i should be changing the source variable to something so that it doesn't keep picking the same neighbors.
neighbors returns a set of the vertex numbers that have an edge between source and neighbor.
if there are any further questions about the code, i'll try and answer them, but i'm kinda lost right now.
Code:
void shortest(graph<string> g, int source)
{
int maximum = g.max(); //number of possible vertices in the graph
vector<int> distance(g.size());
vector<int> predecessor(g.size());
string temp3;
int next=0;
int min=0;
int min_vertex = 0;
int sum=0;
int v=0;
//step 1: fill distance array with -1 except for source, which is 0
for (int i=0;i<g.size();i++)
{
distance[i] = -1;
}
distance[source] = 0;
//step 2: initialize set of vertices to empty set
set<int> allowed_vertices;
//step 3:
//3a.: next is the closest vertex to source which isn't in allowed_vertices set yet
for (int allowed_size=1; allowed_size<=g.size(); ++allowed_size)
{
set<int> closest = g.neighbors(source); //set of all neighbors to source,
//the above is the part that finds the connected vertices and the part that i think might have to change the parameter to neighbor?
min= g.is_edge(source, *closest.begin()); //is_edge returns an int, if the value is -1 the path isn't possible
min_vertex=*closest.begin();
for (set<int>::iterator it = closest.begin();it !=closest.end(); it++)
{
if (g.is_edge(source, *it)<min && g.is_edge(source, *it)!= 0)
{
if (allowed_vertices.count(*it)==0)
{
min=g.is_edge(source, *it);
min_vertex=*it;
}
}
}
next=min_vertex; //setting closest neighboring vertex
//3b.: add next to allowed_vertices
allowed_vertices.insert(next);
//3c.: revise distance array so next appears on permitted path
for (v=0;v < g.size(); ++v)
{
if ((allowed_vertices.count(v) == 0) && (g.is_edge(next, v)!=-1))
{
sum = distance[next]+g.is_edge(next, v);
// if (sum < distance[next])
distance[v] = sum;
predecessor[v] = next;
}
}
}
//4.: output values in distance array
// testing
cout<<"here are the distance vector values:" <<endl;
for (int zz=0;zz<distance.size();zz++)
{
cout<<distance[zz] <<" ";
}
cout<<endl;
cout<<"here are the predecessor vertex values:" <<endl;
for (int zzz=0;zzz<predecessor.size();zzz++)
{
cout<<predecessor[zzz] <<" ";
}
cout<<endl;
system("PAUSE");
// /testing
int vertex_on_path = v;
cout<<vertex_on_path <<endl;
while (vertex_on_path!= source)
{
vertex_on_path = predecessor[vertex_on_path];
g.label_vertex(vertex_on_path, temp3); //error on this line
cout<<temp3 <<endl;
}
}