//s is the vertex to start from
void Graph::dijkstra(int s)
{
//for every vertex v, set dist to infinity and known to false
for(int v = 0; v < adjList.size(); v++)
{
adjList[v].dist = 999999;
adjList[v].known = false;
adjList[v].path = -1;
}
//set start's dist to 0 (zero cost to travel to self)
adjList[s].dist = 0;
adjList[s].path = s;
//using a priority queue with pairs as the element
//pair's first is a vertex's dist, with second being the vertex index
//only these two pieces of information are needed, so inserting the entire
//Vertex node would be wasteful
LeftistHeap< pair<double,int> > p;
pair <double, int> temp (adjList[s].dist, s); //insert start
p.insert(temp);
for( ; ; )
{
pair <double,int> temp1; //temporary pair for later use
int v; //the index of the Vertex v
bool success = false; //success is true when we are done
//while the priority queue is not empty and success is false
while(!p.isEmpty() && !success)
{
p.deleteMin(temp1); //v will be passed by ref and get the minVal
v = temp1.second; //Vertex v is the smallest unknown distance vertex
if(!adjList[v].known) success = true; //set v's known to true
}
if(!success) break;
//
adjList[v].known = true;
//for each Vertex w adjacent to v
for(int i = 0; i < adjList[v].adj.size(); i++)
{
double vdist = adjList[v].dist; //vertex v's dist
double w = adjList[v].adj[i].vertex; //vertex w's position in adjList
double wdist = adjList[w].dist; //vertex w's dist
double cvw = adjList[v].adj[i].weight; //weight of edge between v and w
//if the new dist is better, update the dist and PQ
if(vdist + cvw < wdist)
{
adjList[w].dist = vdist + cvw;
pair<double, int> temp2 (adjList[w].dist, w);
p.insert(temp2);
adjList[w].path = v;
}
}
}
}
I want to edit the Dijkstra algorithm I implemented to get the maximum flow from vertex A to B, where edge weights are interpreted as flow capacities.
The book tells me a minor alteration to Dijkstra can be made to obtain the augmented path needed for the max network flow problem. However, the book fails to tell me what I need to change. Apparently it is supposed to be something obvious, but I am failing to see where I should alter my code.
The augmented path would be the path of maximum flow, where maximum flow is determined by the minimum edge of the path. Basically, I want the code to choose the path where the maximum flow is optimal, so choosing the best flow at each stage. In this case the edge's weight is its flow capacity, so I want to travel the edges that allow me to have maximum flow at the end. So instead of reaching a sum of distance, I want to have max flow where the minimum edge weight determines the max flow.
Dijkstra takes at each step the node with minimum "distance", and expand that node.
To calculate the distance it uses the "sum" of the weights of the nodes.
In this case you need to redefine minimum and sum.
The "sum" will be min( e_j ) of the path.
¿Do you realize what will be the "minimum? (next node to expand)
Keep in mind that it's a greedy algorithm, that works because there aren't negative weights.
So to expand a node you need to be sure that there can't be another path that leads there with less cost.