FAQ Database Discussion Community


Can Bellman-Ford algorithm be used to find shorthest path on a graph with only positive edges?

algorithm,graph-algorithm,dijkstra,bellman-ford
I know that Dijkstra's algorithm can be used only on positive lengths of edges, and Bellman-Ford can be used when the graph also has negative ones. Suppose we have a graph with only positive edges, though. Will Bellman-Ford give the same results as Dijkstra?...

Wraping of equispaced point set in a given direction

java,r,algorithm,geospatial,graph-algorithm
Let us consider a 2-D (latitude, longitude) point set. The points in the set are equispaced (approx.) with mutual distance 0.1 degree \times 0.1 degree . Each point in the set is the centre of a square grid of side length 0.1 degree (i.e., intersect point of two diagonals of...

Minimal spanning tree with degree constraint

algorithm,graph,graph-algorithm,minimum-spanning-tree,degrees
I have to solve this problem: Given a weighted connected undirected graph G=(V,E) and vertex u in V. Describe an algorithm that finds MST for G such that the degree of u is minimal; the output T of the algorithm is MST and for each another minimal spanning tree T'...

Can a non-oriented graph have more than one Eulerian cycle?

graph-theory,graph-algorithm
I know that my question is more about graphs than programming but, I like the community here which is very active and you guys may have work with graphs. So here Im wondering if the set of the Eulerian cycle of a non-oriented graph can contain more than one. Thanks...

How to design an O(m) time algorithm to compute the shortest cycle of G(undirected unweighted graph) that contains s?

graph-algorithm
How to design an O(m) time algorithm to compute the shortest cycle of G(undirected unweighted graph) that contains s(s ∈ V) ?

Compute costs only of paths between all pairs in weighted graph

algorithm,graph-algorithm
Is there an algorithm faster than O(n2) for computing the costs only between every pair in a weighted non-cyclic graph, assuming I do not need the shortest paths but just the paths I would get if using simple BFS? I do not need the actual paths, only the costs of...

Generate states for depth first search

java,algorithm,graph,graph-algorithm,depth-first-search
So while practicing on USACO, I got stuck on this question. Question Description : There are N lamps in the room (all are initially switched on). There are 4 switches for the lamps with each switch toggles specific lamps like: Switch 1 : Toggles all the lamps Switch 2 :...

PageRank toy example fails to converge

python,web-crawler,graph-algorithm,pagerank
I'm coding a toy PageRank, including a crawler as well. It looks a bit odd, as my code fails to converge the PR values. I can also note that the delta between each iteration is 0, part of the output would be: url: http://en.m.wikipedia.org/wiki/Israel_State_Cup links_to_node: set(['http://en.m.wikipedia.org/wiki/Association_football', 'http://en.m.wikipedia.org/wiki/Wikipedia:General_disclaimer']) links_from_node: set(['http://en.m.wikipedia.org/wiki/Israel_State_Cup']) PR_score:...

When adding a random edge to a graph, which bridge edges are not bridge edges any longer?

algorithm,graph,graph-algorithm
A random edge e is added to a graph. It happens to not be a bridge edge. Let C be the connected component of the endpoints of e. Given the list L of all the bridge edges of C (before e was added), which is the fastest algorithm to find...

Algorithm for finding the path that minimizes the maximum weight between two nodes

algorithm,graph,graph-algorithm,shortest-path
I would like to travel by car from city X to city Y. My car has a small tank, and gas stations exist only at intersections of the roads (the intersections are nodes and the roads are edges). Therefore, I would like to take a path such that the maximum...

Algorithm like Bellman-Ford, only for multiple start, single destination?

algorithm,graph,graph-algorithm,path-finding,bellman-ford
Algorithms like the Bellman-Ford algorithm and Dijkstra's algorithm exist to find the shortest path from a single starting vertex on a graph to every other vertex. However, in the program I'm writing, the starting vertex changes a lot more often than the destination vertex does. What algorithm is there that...

How to apply Dijktra algorithm on this graph?

algorithm,graph-algorithm
How to apply dijkstra algorithm on this graph? I've been trying, but I cant figure out hows it going? For example if we are to find shortest path from a to c, then shouldn't it be 3 as the shortest one go from a to b (1) and then b...

Find a MST in O(V+E) Time in a Graph

algorithm,graph,graph-algorithm,minimum-spanning-tree
Similar question has been asked before, as in http://cs.stackexchange.com/questions/28635/find-an-mst-in-a-graph-with-edge-weights-from-1-2 The question is: Given a connected undirected graph G=(V,E) and a weight function w:E→{1,2}, suggest an efficient algorithm that finds an MST of the graph in O(V+E) without using Kruskal. I had a look at the suggested solutions on the thread...

Heuristic to find the maximum weight independent set in an arbritary graph

algorithm,graph,graph-algorithm,linear-programming,np-complete
The MWIS (Maximum weight independent set) is a NP-complete problem, so if P!=NP we cannot find a solution in a good enough time complexity. I am looking for an algorithm that can find an approximation of the MWIS in an arbitrary graph within a good time complexity. I am currently...

Graph Theory - Length of Cycle UnDirected Graph - Adjacency Matrix

algorithm,graph,graph-algorithm
Study Review Question for comprehensive Exam for algorithms part. Let G be an undirected Graph with n vertices that contains exactly one cycle and isolated vertices (i.e. no leaves). That means the degree of a vertex is 0 (isolated) if it is not in the cycle and 2 if it...

Undirected, weighted graph partitioning

algorithm,language-agnostic,graph-algorithm
I need to partition a graph in such a way that node X and node Y are no longer connected. Additionally, the sum of the weights of the removed edges must be the lowest one possible. For example: 3 1 2 X ----- Z ----- W ----- Y Should become:...

Graph algorithm to collect all edges which are on any path between two nodes

algorithm,graph,graph-algorithm
I need to find all edges which are on any path between two nodes [src, dest] in a directed graph. Means that each edge (from base to head) has to satisfy: there is a path from src to base there is a path from head to dest I could collect...

Best graph algorithm for least transfer in an electric grid

c++,graph,graph-algorithm
I'm given a series of cities, and each one produces an amount of electricity and needs an amount of electricity. Each city has up to 8 adjacent cities, and I am trying to minimize the number of transfers. If A->B 10 energy, total cost of transfer is 10. If A->B->C...

How to use heaps with dictionaries to implement single source shortest path algorithm?

python,algorithm,dictionary,graph-algorithm,dijkstra
I chose to represent my graph as a nested dictionary: graph = {'A': {"B": 20, 'D': 80, 'G' :90}, 'B': {'F' : 10}, 'F':{'C':10,'D':40}, 'C':{'D':10,'H':20,'F':50}, 'D':{'G':20}, 'G':{'A':20}, 'E':{'G':30,'B':50}, 'H':{}} And from a previous question, I was instructed to use heaps to implement the dijkstra single source shortest paths algorithm. The...

Datastructure related. Find all arrays elements greater than or equal to given input

java,algorithm,data-structures,graph-algorithm
I have a long sequence of order amounts, 1000, 3000, 50000, 1000000, etc. I want to find out all orders whose amount is more than 100000. Simplest solution can be iterate through full list and compare and put matched on into another list which will give you all whose amount...

What data structure or design pattern to use to map a defined sequence of steps

java,oop,design-patterns,graph-algorithm
We have a java application that processes different types of financial transactions. These transactions have different flows and for system flexibility(esp user) we introduced an xml that we use to define the transaction flow for each. The steps are executed asynchronously The xml looks like this <transaction code="201510" name="deposit"> <step...

Finding the number of edges and performing a topo sort in my graph implementation

c++,graph,graph-algorithm,topological-sort
I have been working on a graph implementation for the last few days. All of this is really new to me, and I am stuck on two parts of my implementation. I am implementing a digraph of courses from an input file. From the file, I can determine which courses...

How I can represent a graph in java? [closed]

java,algorithm,graph,graph-algorithm
I have this graph in graph S and P take values{1,2,3,4,5} I want to represent this graph in java can you help me with idea? thank you in advance...

Getting a DFS from a BFS?

algorithm,search,data-structures,graph-algorithm
Is it possible to get a DFS doing a BFS search? If I just use a stack and then pop them out wouldn't it come out in DFS order? I am trying to do a DFS search but I only have an adjacency list with outgoing edges, so I don't...

Partially coloring a graph with 1 color

algorithm,graph,graph-algorithm
I just started reading graph theory and was reading about graph coloring. This problem popped in my mind: We have to color our undirected graph(not completely) with only 1 color so that number of colored nodes are maximized. We need to find this maximum number. I was able to formulate...

Number of unique sequences of 3 digits (-1,0,1) given a length that matches a sum

algorithm,math,graph-algorithm
Say you have a vertical game board of length n (being the number of spaces). And you have a three-sided die that has the options: go forward one, stay and go back one. If you go below or above the number of board game spaces it is an invalid game....

How to start Dijkstra's algorithm on a graph stored in a dictionary

python,algorithm,dictionary,graph-algorithm,dijkstra
I want to implement Dijkstra's shortest-path algorithm, and I'm using a multi-level dictionary to represent my graph. For example: g = {'A': {'C': 2}, 'B': {'B': 4, 'A': 2}} I know how to access the inner dictionary using double for loops. But if the user inputs a starting point and...

applying a function to graph data using mapReduceTriplets in spark and graphx

scala,network-programming,apache-spark,graph-algorithm,spark-graphx
I'm having some problems applying the mapReduceTriplets to my graph network in spark using graphx. I've been following the tutorials and read in my own data which is put together as [Array[String],Int], so for example my vertices are: org.apache.spark.graphx.VertexRDD[Array[String]] e.g. (3999,Array(17, Low, 9)) And my edges are: org.apache.spark.graphx.EdgeRDD[Int] e.g. Edge(3999,4500,1)...

Detect cycle in a graph using Kruskal's algorithm

c++,algorithm,graph-algorithm,disjoint-sets,union-find
I'm implementing Kruskal's algorithm, which is a well-known approach to finding the minimum spanning tree of a weighted graph. However, I am adapting it to find cycles in a graph. This is the pseudocode for Kruskal's algorithm: KRUSKAL(G): 1 A = ∅ 2 foreach v ∈ G.V: 3 MAKE-SET(v) 4...

Shortest paths with 2 constraints (Weight and Colour)

algorithm,graph,graph-theory,graph-algorithm,dijkstra
Input: We have a directed graph G=(V,E) and each edge has a weight and a colour {red,green}. We are also given a starting node s.Problem/Algorithm: Can we find for all u edges of G, the shortest paths s-u with at most k red edges ? First approach: We save for...

Algorithm to find k neighbors in a certain range?

algorithm,data-structures,graph-algorithm,nearest-neighbor,point-clouds
Suppose there is a point cloud having 50 000 points in the x-y-z 3D space. For every point in this cloud, what algorithms or data strictures should be implemented to find k neighbours of a given point which are within a distance of [R,r]? Naive way is to go through...

Shortest paths that are impossible for BFS to find?

algorithm,search,graph-theory,graph-algorithm,breadth-first-search
I took an exam earlier and there was a question that baffled me and everyone else I talked to. It asked the following: Give an example of an unweighted graph G and two vertices s and f such that there is a shortest path between s and f that breadth-first...

Java: Uniform Cost Search with Node class

java,graph-algorithm,priority-queue,comparable
The below code is supposed to detect an image, create a 2d array containing the pixel values from that image, and determine the path of lowest cost (I used Uniform Cost Search) from a Point A inside the image to a Point B inside the image. When I run my...

To print the boundary of Binary Tree

algorithm,tree,binary-tree,binary-search-tree,graph-algorithm
I have been asked in an interviews to print the boundary of the Binary Tree. For example. 1 / \ 2 3 / \ / \ 4 5 6 7 / \ \ 8 9 10 Answer will be : 1, 2, 4, 8, 9, 10, 7, 3 I have...

A Dynamic Programming or Graph Algorithm, a Nice Questions

algorithm,math,graph,dynamic-programming,graph-algorithm
An agent is works between n producer and m consumers. ith producer, generates s_i candy and jth consumer consumes b_j candy in this year. For each candy that sales, agent get 1 dollar payoff. For some problems, one strict rule was defined that a producer should be sales candy to...

Iterative version of the Bron–Kerbosch algorithm?

algorithm,graph-algorithm,pseudocode
The Bron–Kerbosch algorithm is a method for listing all maximal cliques of a graph. I recently implemented the algorithm successfully just for fun. The downside is that the algorithm is recursive, and thus can only be ran on tiny graphs until the stack overflows. It should be possible to make...