The single source shortest path problem and some background

The Single Source Shortest Path (sssp) problem asks about finding the shortest path to all vertices from a given source vertex in a graph. So, how is it different from our Dijkstra's algorithm? Well, this graph is allowed to have negative edges. Why can Dijkstra's fail in the presence of negative edges? I guess we need to first start with Dijkstra's to understand it's shortcomings. So, a little about what Dijkstra does first.

Hey! No need, it does exactly the same thing sssp. So, now why do we need this? I guess we will need to code this down to talk more about it.

Here goes Dijkstra's .Oh!Wait, We will need a priority queue for Dijkstra's. So, Let's start with a priority queue- A min-Heap.

A min-Heap is a binary tree with the property that the parent is always less than the children.

Before we reach a heap, let us try to do this with our understanding of primitive data structures only. Let us first try to do a Dijkstra with no heap.

Little touch up to the concepts of how we make a data structure for a graph first: There are two popular mechanisms: Adjacency matrix and Adjacency list. As the name suggests, adjacency matrix is a matrix. It is a two-dimensional and has the dimensions of the number of the vertices of the graph on each side. Each number in the matrix(say A[i][j]) will denote the weight of an edge between the vertices i and j if such a vertex exists.

The other representation, called an adjacency list, stores the edges as a list and each vertex has an entry to denote the edge numbers which are connected to it.

Which of the two do we choose? As usual, the answer is "choose wisely". A matrix representation takes nxn memory where n is the number of vertices. A matrix representation also taken time O(n) to find all edges incident from/to a vertex. A look up for a cost of an edge between vertices however is an O(1).  An adjacency list on the other hand takes up size proportional to number of edges. Also, an adjacency list can fetch all edges from/to a vertex without having to traverse O(n).

I will discuss about a list representation, it has edges and vertices. Here is a sample implementation of an edge
 
    class edge{
        public edge(int vertex1, int vertex2, int weight2) {
            this.vertices[0] = vertex1;
            this.vertices[1] = vertex2;
            this.weight = weight2;
        }
        int weight;
        int[] vertices = new int[2];
    }

Here is my vertex class, which I have called a node(now I think this is a mistake, vertex should be a subclass of type node):
  import java.util.ArrayList;

class node{
 int number;
 ArrayList<Integer> edges = new ArrayList<Integer>();

  node(int num){
this.number = num;
  }
}

Back to a little about Dijkstra's. I assume that we need to find the SSSP from vertex 0 without loss of generality. I maintain a distance parameter from each vertex which we initialize with a huge number. However, since the distance to vertex 0 from 0 is 0, so cost to vertex zero is set to 0. I use a numbered flag to indicate how many vertices I have processed. There is one main for loop in which the numbered flag is incremented each time. In the loop,  we find the vertex closest to the source which is not processed, relax it(that is considering this new distance, we change the corresponding distances if they are less than the earlier ones).

Here is the code:
public void getDijkstra(){
int processed = 0;

while(processed<vertices.length){
flag = 1;
Arrays.sort(vertices);
int currVertexNum = vertices[processed].vertexNum;
flag = 0;
Arrays.sort(vertices);
for(int e:nodeList[currVertexNum].edges){
int otherEnd = edgeList[e].vertices[0] == currVertexNum? edgeList[e].vertices[1]: edgeList[e].vertices[0];
if(vertices[currVertexNum].dist!=Integer.MAX_VALUE &&vertices[currVertexNum].dist+edgeList[e].weight<vertices[otherEnd].dist)
vertices[otherEnd].dist = vertices[currVertexNum].dist+edgeList[e].weight;
}
processed++;

}


}
Dijkstra's relies on the fact that if we have a set of neighbours from one vertex, the cheapest distance to that neighbour cannot get any cheaper. But, what if we have negative edge costs? Then, for a vertex v, if we have neigbhours w and x, and x is cheaper, then cost from source to x will be cost from source to v and cost from v to x. However, if we have negative edges, we might find a path from v->w->(some more negative edges)->x which might be cheaper than the earlier one. Hence, Dijkstra babu gives up on negative edges.

//more analysis on negative edges to be filled here.

 So, the need for another algorithm for graphs with negative edge costs!!Follow up on bellman needs to be updated and some heapifying stuff too

The bellman ford algorithm , as other DP problems, relies on breaking down the SSSP problem into subproblems. The main recurrence relies on counting the number of edges from the source to a vertex being considered. The maximum shortest path between two vertices would go through all the vertices. Thus, the length of that path would be atmost (vertex count - 1) . The shortest distance from a source to a destination when using k edges can thus either be the shortest distance we get when we consider k-1 edges or it can be the shortest distance from a destination which has an incoming edge to the destination. Using this recurrence, we solve the bellman ford. Little subtle point to note : when using Dijkstra's we look at outgoing edges, when using bellman's we want incoming, so it would be better to change the data structure according to the algorithm.

private int manford(int destination, int maxEdges) {

System.out.println("destination "+destination+" Maxedges "+maxEdges);
if(cost[destination][maxEdges] != Integer.MAX_VALUE || maxEdges==0)
return cost[destination][maxEdges] ;
node dest = nodeList[destination];

int tempMin = manford(destination,maxEdges-1);

for(int e: dest.edges){
int restPlace = edgeList[e].vertices[0] == destination? edgeList[e].vertices[1]: edgeList[e].vertices[0];
int coster = manford(restPlace,maxEdges-1);
if(coster<Integer.MAX_VALUE)
tempMin = tempMin < coster+edgeList[e].weight?tempMin:coster+edgeList[e].weight;
}

cost[destination][maxEdges] = tempMin;
return tempMin;
}

Here is a link to my git repo for the full codes.