The tag has no wiki summary.

learn more… | top users | synonyms

-2
votes
0answers
46 views

Cut the Execution Time Two Times in All-Pair Shortest Path by Using Dijkstra Algorithm [closed]

Complexity of finding single-source shortest path in a simple undirected weighted graph with Dijkstra algorithm (assume that priority queue uses a heap data structure) is: O((n+m)logn) {n - the ...
4
votes
1answer
106 views

Is this Wikipedia pseudocode for in-order generic tree traversal correct?

Wikipedia states that the following algorithm works for any tree (not necessarily binary trees) Perform pre-order operation For each i (with i = 1 to n) do: Visit i-th, if present ...
4
votes
2answers
69 views

Mutation operator for genetic algorithms for solving traveling salesman problem

I need help help for defining mutation operator for traveling salesman problem. I'm currently using this now (pseudocode): mutate ( strand ): for n in random_interval ( min_gene_index, ...
0
votes
1answer
141 views

Big graph traversal with OOP

I'm trying to solve a algorithmic contest's problem. I have a matrix 2000x2000. I want to represent it as graph and traverse it with BFS/DFS. I have time limits on app running (2s). Simple vertices ...
7
votes
3answers
204 views

Algorithm or domain for finding cheapest subgraphs that connect vertex pairs

I am currently working on a project inspired by the Ticket to Ride board game. This board game is played on an undirected graph where each vertex represents a city and each edge represents a ...
4
votes
1answer
90 views

Mathematically correct A* heuristic / distance estimator for a latitude / longitude graph

I have a graph in which each node is a geographical point on the surface of the earth, defined by it's latitude / longitude coordinates. Correct ways to calculate the distance between two such points ...
0
votes
1answer
226 views

Shortest path to visit all nodes [duplicate]

I am given a set of tourist attractions(nodes identified by x, y) and i need to find the shortest path to visit them. The way i thought of it, is i will ignore if there are streets available and ...
3
votes
0answers
90 views

In a mutual credit network, how would you program an automatic jubilee?

A little explanation might be needed. I mean mutual credit the way that it's defined here: a type of alternative currency in which the currency used in a transaction can be created at the time of ...
0
votes
1answer
226 views

Number of sequences when no adjacent items can be the same

I came across this one problem, There is a particular sequence only uses the numbers 1, 2, 3, 4 and no two adjacent numbers are the same. Write a program that given n1 1s, n2 2s, n3 3s, n4 4s ...
0
votes
1answer
270 views

how to traverse towards child node from parent node in n-ary tree? [closed]

In an n-ary tree... Given a reference to some child node And a reference to a distant parent of the referenced child node Is there a method that a parent node can use to figure out which of its ...
1
vote
2answers
488 views

Looking for an algorithm to connect dots - shortest route

I have written a program to solve a special puzzle, but now I'm kind of stuck at the following problem: I have about 3200 points/nodes/dots. Each of these points is connected to a few other points ...
2
votes
4answers
1k views

Finding the shortest path through a digraph that visits all nodes

I am trying to find the shortest possible path that visits every node through a graph (a node may be visited more than once, the solution may pick any node as the starting node.). The graph is ...
1
vote
1answer
120 views

City exploration algorithm

The purpose of the algorithm is to create n routes on a geographical map, where n is being given, whereas all routes take no longer than t time units by foot and end where they start, while trying to ...
2
votes
0answers
237 views

Understanding Tarjan's Bridge-finding algorithm

Tarjan's algorithm for finding bridges in a graph is found here: http://en.wikipedia.org/wiki/Bridge_(graph_theory)#Tarjan.27s_Bridge-finding_algorithm. However, I don't understand the condition for ...
2
votes
1answer
206 views

Improving the running time of Breadth First Search and Adjacency List creation

We are given an array of integers where all elements are between 0-9. have to start from the 1st position and reach end in minimum no of moves such that we can from an index i move 1 position back and ...
6
votes
1answer
187 views

Heuristic Approach for Flexible DIFF Implementation

I have created a DIFF implementation to compare document revisions at work. It is based on An O(ND) Difference Algorithm and Its Variations. One thing that has become important is to take the list ...
1
vote
2answers
1k views

Is Pre-Order traversal same as Depth First Search?

It seems to me like pre-order traversal and DFS are same as in both the cases we traverse from root till the left branch and back to root and then to the right branch recursively. Could any please ...
5
votes
5answers
575 views

Finding most Important Node(s) in a Directed Graph

I have a large (≈ 20 million nodes) directed Graph with in-edges & out-edges. I want to figure out which parts of of the graph deserve the most attention. Often most of the graph is boring, or at ...
0
votes
2answers
610 views

What graph traversal algorithm should I use?

I would like to write an algorithm which can traverse a graph and hopefully later I can implement it to use for an indoor navigation system. The graph would come from floor plans of a building and ...
2
votes
2answers
292 views

Graph traversal and filtering in indoor navigation and path finding

Which of the following options take less processing time/is less expensive in a graph traversal algorithm for a (indoor)navigation system? a) To produce all possible paths between start and ...
3
votes
2answers
655 views

Breadth-first graph search problem

I thought I was doing breadth-first graph search correctly, but my instructor's grading script is telling me that my answer is incorrect. From the instructions: Consider a breadth-first graph ...
7
votes
4answers
214 views

Graph theory problem (name unknown)

I am trying to solve the following kind of problem. I do not know if there is already a name for this, or a solution; however, I'm willing to bet there is. I was hoping someone could point me in the ...
1
vote
1answer
428 views

Languages with graph data structures and algorithms in standard library

I am trying to improve my knowledge and ability with graphs and graph algorithms and have noticed something curious: as far as I can tell no "mainstream" language contains support for graphs in its ...
6
votes
3answers
6k views

Usefulness of pre and post order traversal of binary trees

This may be very naive, but I was wondering, it the context of binary trees (plain, sorted and balanced), of all the traversal types: depth-first pre-order depth-first in-order depth-first ...
2
votes
1answer
818 views

Architecture for Social Graph data that has a Time Frame Associated?

I am adding some "social" type features to an existing application. There are a limited # of node & edge types. Overall the data itself is relatively small (50,000 - 70,000 for each type of ...
6
votes
5answers
486 views

Finding an A* heuristic for a directed graph

In a previous question, I asked about finding a route (or path if you will) in a city. That is all dandy. The solution I chose was with the A* algorithm, which really seems to suit my needs. What I ...
0
votes
2answers
233 views

Algorithm for searching the neighbors neighbor of a directed graph

Is there an algorithm to search a directed graph (tree) for its neighbors neighbor? My current brute-force solution works as follows: for each node n: for each child c of n for each parent ...
1
vote
1answer
820 views

Gremlin — do I have to know Java/Groovy

This is the excerpt from the project's Github page. Gremlin provides graph traversal related syntactic sugar to Groovy. Groovy provides dynamic language syntactic sugar to Java. Realize that ...