Given an aribtrary graph (possibly with negative weight edge, but no negative weight cycle) and two nodes A and B in the graph. Find the shortest path from A to B with an even number of edges. The graph has at most 1000 vertices and 10000 edges.


note: if we were to ignore the fact that the path length must be even then bellman ford will work!
(P.S. I made bellman ford far more verbose than Robert did)

bellman ford:


int dist[];
vector<int> graph[];
cost[][];

void bellman_ford(int source){

memset(dist, 0x3f, sizeof(dist));
dist[source]=0;
bool relax=true;

     while(relax){
      relax = false;
          for(int nodei =0; nodei<V; nodei++){
              for(int j=0; j<graph[i].size(); j++){
                   int nodej = graph[i][j];
                   if(dist[nodej] > dist[nodei] + cost[nodei][nodej]){
                     dist[nodej] = dist[nodei] + cost[nodei][nodej];
                     relax = true;
                   }
               }
          }
     }
     
}


note that if we want to keep track of lengths then:


int length[]; //initialize to 0's;
int dist[];
vector<int> graph[];
cost[][];

void bellman_ford(int source){

memset(dist, 0x3f, sizeof(dist));
dist[source]=0;
bool relax=true;

     while(relax){
      relax = false;
          for(int nodei =0; nodei<V; nodei++){
              for(int j=0; j<graph[i].size(); j++){
                   int nodej = graph[i][j];
                   if(dist[nodej] > dist[nodei] + cost[nodei][nodej]){
                     length[nodej] = length[nodei] + 1;
                     dist[nodej] = dist[nodei] + cost[nodei][nodej];
                     relax = true;
                   }
               }
          }
     }
     
}

Notice that we always relax an edge if we can find a better path:


if(dist[nodej] > dist[nodei] + cost[nodei][nodej]){
 length[nodej] = length[nodei] + 1;
 dist[nodej] = dist[nodei] + cost[nodei][nodej];
 relax = true;
}

What if we just added another constraint when relaxing the destination node:

Attempt 1:

if((dist[nodej] > dist[nodei] + cost[nodei][nodej]) &&
   (nodej != destination || ((length[nodei] +1)%2)==0 )){ //make it so that we can only relax 
                                                          //the destination edge if it forms an even length path 
 length[nodej] = length[nodei] + 1;
 dist[nodej] = dist[nodei] + cost[nodei][nodej];
 relax = true;
}


Excersise:
Find out what's wrong with attempt 1, and find a counter-example.


Hint: Do we want the strict inequality?
If we only relax an edge when we find something strictly less than, we are ignoring
some important cases. We might be ignoring a possible even length path.

So essentially we need to consider paths of all lengths that lead to an optimal solution.


Attempt 2:

bool repeats[]; //If an odd optimal path and an even optimal path 
                //exist then repeats[node]=true (sorry for the bad naming)
                //initialize to false
                
int length[]; //initialize to 0's;
int dist[];
vector<int> graph[];
cost[][];

void bellman_ford(int source, int destination){

memset(dist, 0x3f, sizeof(dist));
dist[source]=0;
bool relax=true;

     while(relax){
      relax = false;
          for(int nodei =0; nodei<V; nodei++){
              for(int j=0; j<graph[i].size(); j++){
                   int nodej = graph[i][j];
                   if((dist[nodej] >= dist[nodei] + cost[nodei][nodej])&&(nodej != destination 
                     || ((length[nodei] +1)%2)==0 )|| repeats[nodei]){
                        
                      //if there are optimal odd and even path exist then there are "repeats"  
                      if((dist[nodej] == dist[nodei] + cost[nodei][nodej]) 
                                                && (length[k]%2)==(length[j]%2) {
                       repeat[nodej] = true;
                       
                      }else{
                      //otherwise there are odd and even paths 
                      //iff the previous vertex of new path has odd and even optimal paths
                      //one relaxed edge had odd and even paths
                      repeat[nodej] = repeat[nodei];
                      }
                      
                      
                      length[nodej] = length[nodei] + 1;
                      dist[nodej] = dist[nodei] + cost[nodei][nodej];
                      relax = true;
                   }
               }
          }
     }
     
}
////////////////////////////

notice that the shortest path algorithm doesn't necessairly produce the shortest path for all the nodes anymore. It does however get the
shortest even length path for the destination path. You can get both with a little modification of the code. 


/////////////////////////////////////////////

Next I want to show an example of DFS used to solve a soduku

I always tend to think of DFS as being guess and test. Pretend the other methods called are implemented

//depth stores the number of empty squares
//

	private int sodukuSolve() throws SolutionFoundException {
		if (depth == 0) {
			throw new SolutionFoundException();
		}
		int position = getPositionOfHighConstraint();
		int row = position / grid.length;
		int col = position % grid.length;
		for (int i = 1; i <= grid.length; i++) {
			grid[row][col] = i;
			if (isConsistant(row, col)) {
				depth--;
				sodukuSolve();
			}
		}
		depth++;
		grid[row][col] = 0;
		return 0;
	}