Dijkstra's algorithm implement

Question

I have seen dijkstra's algorithm for weighted graphs what should I do to implement that to find shortest path in an unweighted graph?

Should i consider weights between all edges 0 or 1?

Secondly I want to implement a bfs on 10^5 nodes to check whether a node is reachable from any other node? Is it possible, as defining a 2-D array of [10^5][10^5] gives a memory fault.

Answer 1

For your first question, I did implement Dijkstra on unweighted path with weights of 1, it's working fine, but there may be a better solution.

I don't remember much about bfs, sorry !

Answer 2

You can think of an unweighted graph as every edge having a weight of 1.

For the BFS on a big graph, have a look at big data algorithms which use "external" memory (hard disk) to store the complete graph and use efficient data access tricks to this data such that the parts the algorithm works on does fit in the memory. for a start see: http://www.win.tue.nl/~hermanh/teaching/2IL35/AMM/04-elementary-graph-algorithms.pdf

Answer 3

Using 0 as the cost of the arcs would result in a equal cost for every possible path in the graph and therefore anyone could be the shortest.

Using 1 means that all of your arcs have the same cost, so Dijkstra will find the path which minimizes the number of arcs between your begin and your goal. Of course, it may happen that several paths fit that condition, so the algorithm will return one of them.

I hope my answer helps.