How to modify Dijkstra to obtain augmented path

My textbook provided pseudocode for the Dijkstra algorithm, which I implemented as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
struct Edge
{
	int vertex; //index of vertex in the adjList vector
	double weight; //weight of edge
	
	Edge(int v, double w): vertex(v), weight(w){};
};

struct Vertex
{
	vector<Edge> adj; //list of vertices adjacent
	bool known; //indicates if shortest path dist has been determined
	double dist; //shortest path distance, calculated by dijkstra
	double fat;
	int path; //index of previous vertex in shortest path
};

class Graph
{
	private:
		vector<Vertex> adjList; //master adjacency list of all vertices
		void dijkstra(int s); //internal method for dijsktra
		void augmented(int a, int b); //internal method for augmented path
		
	public:
		Graph(); //default constructor
		Graph(string fileName); //constructor, parses input file into adjList
		~Graph(); //destructor
		void dijkstra(); //shallow dijkstra
		void augmented(); //shallow augmented path

};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//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.
Define augmented path
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.
Topic archived. No new replies allowed.