Graph Algorithms are a sequence of well-defined steps that will solve a problem related to Graph Theory, where a Graph in this context is a collection of vertices ("nodes") and edges that connect these vertices.
26
votes
4answers
12k views
Negative weights using Dijkstra's Algorithm
I am trying to understand why Dijkstra's algorithm will not work with negative weights. Reading an example on Shortest Paths, I am trying to figure out the following scenario:
2
A-------B
\ ...
13
votes
4answers
2k views
What to use for flow free-like game random level creation?
I need some advice. I'm developing a game similar to Flow Free wherein the gameboard is composed of a grid and colored dots, and the user has to connect the same colored dots together without ...
8
votes
1answer
736 views
OpenGL ES 2.0 Vertex Transformation Algorithms
I'm developing an image warping iOS app with OpenGL ES 2.0.
I have a good grasp on the setup, the pipeline, etc., and am now moving along to the math.
Since my experience with image warping is nil, ...
2
votes
2answers
2k views
Best algorithm to determine if an undirected graph is a tree
What is the time complexity of the Best algorithm to determine if an undirected graph is a tree??
can we say Big-oh(n) , with n vertices??
1
vote
3answers
1k views
Minimum number of days required to solve a list of questions
There are N problems numbered 1..N which you need to complete. You've arranged the problems in increasing difficulty order, and the ith problem has estimated difficulty level i. You have also assigned ...
3
votes
3answers
973 views
2D waypoint pathfinding: combinations of WPs to go from curLocation to targetLocation
Please take a moment to understand my situation. If it is not comprehendable, please tell me in a comment.
I have an ArrayList of Waypoints. These waypoints are not in any order. A waypoint has the ...
2
votes
4answers
149 views
is there is a route from city a to city b in no more than x days?
I was in a trading firm interview, I was asked this question,
you are travelling accross the state in a buses, the buses can stop at any C possible cities and you need to find a way to go from city ...
2
votes
1answer
296 views
Efficiently find all connected subgraphs
Is there an efficient(*) algorithm to find all the connected (induced) subgraphs of a connected undirected vertex-labelled graph?
(*) I appreciate that, in the general case, any such algorithm may ...
1
vote
1answer
649 views
Eppstein's algorithm and Yen's algorithm for k shortest paths
I'm trying to understand exactly how these algorithms work, but I have been unable to find a simple explanation. I would greatly appreciate it if someone could provide or point me to a description of ...
2
votes
3answers
592 views
How can I use the A star algorithm to find the first 100 shortest paths?
How can I use the A star algorithm to find the first 100 shortest paths?
0
votes
1answer
155 views
Graph algorithm in C by reading grids into array
I need to read some objects from console.It is a bit like the battleship game written in C.
Think of it I have a platform of 6x6 array.I am taking the user input from the user and the char 'X' means ...
14
votes
3answers
678 views
Functional implementation of Tarjan's Strongly Connected Components algorithm
I went ahead and implemented the textbook version of Tarjan's SCC algorithm in Scala. However, I dislike the code - it is very imperative/procedural with lots of mutating states and book-keeping ...
14
votes
4answers
674 views
Visualizing set hierarchies as color coded graphs
I have been reading quite a bit on graphing libraries for Java and Javascript lately but I haven't found a good way to do what I want to do.
Essentially I have a hierarchy of sets with regards to a ...
11
votes
7answers
492 views
Computing target number from numbers in a set
I'm working on a homework problem that asks me this:
Tiven a finite set of numbers, and a target number, find if the set can be used to calculate the target number using basic math operations (add, ...
10
votes
1answer
236 views
Graph travelling algorithm
I've got an interesting graph-theory problem. I am given a tree T with n nodes and a set of edges. T is, of course, undirected. Each edge has weight that indicates how many times (at least) it has to ...
