I’ve found the answer to my question in this book. It is the same with Computer wiring problem which occurs repeatedly in the design of computers and other digital systems. The purpose is to minimize the total wire length. So, it is indeed a minimum length Hamiltonian path. What the book suggests is to create … Read more
Topological Sort (From Wikipedia): In graph theory, a topological sort or topological ordering of a directed acyclic graph (DAG) is a linear ordering of its nodes in which each node comes before all nodes to which it has outbound edges. Every DAG has one or more topological sorts. Pseudo code: L ← Empty list where … Read more
There’s a lot of confusion going on here. Based on what the OP says: I’m not limiting the size of the spanning tree to k vertices; rather I know exactly which k vertices must be included in the MST. This is the Steiner tree problem on graphs. This is not the k-MST problem. The Steiner … Read more
Actually, we don’t need an extra queue to store the info on the current depth, nor do we need to add null to tell whether it’s the end of current level. We just need to know how many nodes the current level contains, then we can deal with all the nodes in the same level, … Read more
Here’s a nice description of the Algorithm that also explains the notion of relaxation. The notion of “relaxation” comes from an analogy between the estimate of the shortest path and the length of a helical tension spring, which is not designed for compression. Initially, the cost of the shortest path is an overestimate, likened to … Read more
You should be able to make it much faster by trading off optimality. See Admissibility and optimality on wikipedia. The idea is to use an epsilon value which will lead to a solution no worse than 1 + epsilon times the optimal path, but which will cause fewer nodes to be considered by the algorithm. … Read more
objects and pointers These are just basic datastructures like hammar said in the other answer, in Java you would represent this with classes like edges and vertices. For example an edge connects two vertices and can either be directed or undirected and it can contain a weight. A vertex can have an ID, name etc. … Read more
The reason for using decrease-key rather than reinserting nodes is to keep the number of nodes in the priority queue small, thus keeping the total number of priority queue dequeues small and the cost of each priority queue balance low. In an implementation of Dijkstra’s algorithm that reinserts nodes into the priority queue with their … Read more
The algorithm you have suggested will indeed find the shortest path in this graph, but not all graphs in general. For example, consider this graph: Let’s trace through the execution of your algorithm. First, you set d(A) to 0 and the other distances to ∞. You then expand out node A, setting d(B) to 1, … Read more
I found this page in my search and since cycles are not same as strongly connected components, I kept on searching and finally, I found an efficient algorithm which lists all (elementary) cycles of a directed graph. It is from Donald B. Johnson and the paper can be found in the following link: http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF A … Read more