Search Results

Search found 349 results on 14 pages for 'shortest'.

Page 1/14 | 1 2 3 4 5 6 7 8 9 10 11 12  | Next Page >

• Shortest Common Superstring: find shortest string that contains all given string fragments

  - by occulus

  Given some string fragments, I would like to find the shortest possible single string ("output string") that contains all the fragments. Fragments can overlap each other in the output string. Example: For the string fragments: BCDA AGF ABC The following output string contains all fragments, and was made by naive appending: BCDAAGFABC However this output string is better (shorter), as it employs overlaps: ABCDAGF ^ ABC ^ BCDA ^ AGF I'm looking for algorithms for this problem. It's not absolutely important to find the strictly shortest output string, but the shorter the better. I'm looking for an algorithm better than the obvious naive one that would try appending all permutations of the input fragments and removing overlaps (which would appear to be NP-Complete). I've started work on a solution and it's proving quite interesting; I'd like to see what other people might come up with. I'll add my work-in-progress to this question in a while.

  Read the article

• How to minimize total cost of shortest path tree

  - by Michael

  I have a directed acyclic graph with positive edge-weights. It has a single source and a set of targets (vertices furthest from the source). I find the shortest paths from the source to each target. Some of these paths overlap. What I want is a shortest path tree which minimizes the total sum of weights over all edges. For example, consider two of the targets. Given all edge weights equal, if they share a single shortest path for most of their length, then that is preferable to two mostly non-overlapping shortest paths (fewer edges in the tree equals lower overall cost). Another example: two paths are non-overlapping for a small part of their length, with high cost for the non-overlapping paths, but low cost for the long shared path (low combined cost). On the other hand, two paths are non-overlapping for most of their length, with low costs for the non-overlapping paths, but high cost for the short shared path (also, low combined cost). There are many combinations. I want to find solutions with the lowest overall cost, given all the shortest paths from source to target. Does this ring any bells with anyone? Can anyone point me to relevant algorithms or analogous applications? Cheers!

  Read the article

• Finding all the shortest paths between two nodes in unweighted directed graphs using BFS algorithm

  - by andra-isan

  Hi All, I am working on a problem that I need to find all the shortest path between two nodes in a given directed unweighted graph. I have used BFS algorithm to do the job, but unfortunately I can only print one shortest path not all of them, for example if they are 4 paths having lenght 3, my algorithm only prints the first one but I would like it to print all the four shortest paths. I was wondering in the following code, how should I change it so that all the shortest paths between two nodes could be printed out? class graphNode{ public: int id; string name; bool status; double weight;}; map<int, map<int,graphNode>* > graph; int Graph::BFS(graphNode &v, graphNode &w){ queue <int> q; map <int, int> map1; // this is to check if the node has been visited or not. std::string str= ""; map<int,int> inQ; // just to check that we do not insert the same iterm twice in the queue map <int, map<int, graphNode>* >::iterator pos; pos = graph.find(v.id); if(pos == graph.end()) { cout << v.id << " does not exists in the graph " <<endl; return 1; } int parents[graph.size()+1]; // this vector keeps track of the parents for the node parents[v.id] = -1; // there is a direct path between these two words, simply print that path as the shortest path if (findDirectEdge(v.id,w.id) == 1 ){ cout << " Shortest Path: " << v.id << " -> " << w.id << endl; return 1; } //if else{ int gn; map <int, map<int, graphNode>* >::iterator pos; q.push(v.id); inQ.insert(make_pair(v.id, v.id)); while (!q.empty()){ gn = q.front(); q.pop(); map<int, int>::iterator it; cout << " Popping: " << gn <<endl; map1.insert(make_pair(gn,gn)); //backtracing to print all the nodes if gn is the same as our target node such as w.id if (gn == w.id){ int current = w.id; cout << current << " - > "; while (current!=v.id){ current = parents[current]; cout << current << " -> "; } cout <<endl; } if ((pos = graph.find(gn)) == graph.end()) { cout << " pos is empty " <<endl; continue; } map<int, graphNode>* pn = pos->second; map<int, graphNode>::iterator p = pn->begin(); while(p != pn->end()) { map<int, int>::iterator it; //map1 keeps track of the visited nodes it = map1.find(p->first); graphNode gn1= p->second; if (it== map1.end()) { map<int, int>::iterator it1; //if the node already exits in the inQ, we do not insert it twice it1 = inQ.find(p->first); if (it1== inQ.end()){ parents[p->first] = gn; cout << " inserting " << p->first << " into the queue " <<endl; q.push(p->first); // add it to the queue } //if } //if p++; } //while } //while } I do appreciate all your great help Thanks, Andra

  Read the article

• Getting shortest path between 2 nodes

  - by Xtapodi

  Hello, i want to ask if there is any way to generate the shortest path from node A to node B without generating the shortest paths to all the other nodes (stop when node B is in the examined set) with A-star in QuickGraph. I want to plug QuickGraph into a game and thus generating all the paths is not allowed from the time limitations the environment imposes. Any other suggestions to solve my problem in C# are welcome Thanks in advance, Xtapodi

  Read the article

• Getting shortest path between 2 nodes in quickgraph

  - by Xtapodi

  Hello, i want to ask if there is any way to generate the shortest path from node A to node B without generating the shortest paths to all the other nodes (stop when node B is in the examined set) with A-star in QuickGraph. I want to plug QuickGraph into a game and thus generating all the paths is not allowed from the time limitations the environment imposes. Any other suggestions to solve my problem in C# are welcome Thanks in advance, Xtapodi

  Read the article

• BFS Shortest Path: Edge weight either 1 or 2

  - by Hackster

  I am trying to implement a shortest path algorithm using BFS. That is I am trying to find the shortest path from a specified vertex to every other vertex. However, its a special case where all edge weights are either 1 or 2. I know it could be done with Dijkstra's algorithm but I must use Breadth First Search. So far I have a working version of BFS that searches first for a vertex connected with an edge of weight 1. If it cannot find it, then returns a vertex connected with an edge of weight 2. After thinking about it, this is not the correct way to find the shortest path. The problem is I cannot think of any reasoning why BFS would work with weights 1 or 2, as opposed to any weight. Here is the code: public void addEdge(int start, int end, int weight) { adjMat[start][end] = 1; adjMat[end][start] = 1; edge_weight[start][end] = weight; edge_weight[end][start] = weight; } // ------------------------------------------------------------- public void bfs() // breadth-first search { // begin at vertex 0 vertexList[0].wasVisited = true; // mark it displayVertex(0); // display it theQueue.insert(0); // insert at tail int v2; while( !theQueue.isEmpty() ) // until queue empty, { int v1 = theQueue.remove(); // remove vertex at head // until it has no unvisited neighbors while( (v2=getAdjUnvisitedVertex(v1)) != -1 ){// get one, vertexList[v2].wasVisited = true; // mark it displayVertex(v2); // display it theQueue.insert(v2); // insert it } } // end while(queue not empty) // queue is empty, so we're done for(int j=0; j<nVerts; j++) // reset flags vertexList[j].wasVisited = false; } // end bfs() // ------------------------------------------------------------- // returns an unvisited vertex adj to v -- ****WITH WEIGHT 1**** public int getAdjUnvisitedVertex(int v) { for (int j = 0; j < nVerts; j++) if (adjMat[v][j] == 1 && vertexList[j].wasVisited == false && edge_weight[v][j] == 1){ //System.out.println("Vertex found with 1:"+ vertexList[j].label); return j; } for (int k = 0; k < nVerts; k++) if (adjMat[v][k] == 1 && vertexList[k].wasVisited == false && edge_weight[v][k] == 2){ //System.out.println("Vertex found with 2:"+vertexList[k].label); return k; } return -1; } // end getAdjUnvisitedVertex() // ------------------------------------------------------------- } //////////////////////////////////////////////////////////////// public class BFS{ public static void main(String[] args) { Graph theGraph = new Graph(); theGraph.addVertex('A'); // 0 (start for bfs) theGraph.addVertex('B'); // 1 theGraph.addVertex('C'); // 2 theGraph.addEdge(0, 1,2); // AB theGraph.addEdge(1, 2,1); // BC theGraph.addEdge(2, 0,1); // AD System.out.print("Visits: "); theGraph.bfs(); // breadth-first search System.out.println(); } // end main() } The problem then is, that I don't know why BFS can work for the shortest path problem with edges of weight 1 or 2 as opposed to any edges of any weight. Any help is appreciated. Thanks!

  Read the article

• Algorithm shortest path between all points

  - by Jeroen

  Hi, suppose I have 10 points. I know the distance between each point. I need to find the shortest possible route passing trough all points. I have tried a couple of algorithms (Dijkstra, Floyd Warshall,...) and the all give me the shortest path between start and end, but they don't make a route with all points on it. Permutations work fine, but they are to resource expensive. What algorithms can you advise me to look into for this problem? Or is there a documented way to do this with the above mentioned algorithms? Tnx Jeroen

  Read the article

• A shortest path problem with superheroes and intergalactic journeys

  - by Dman

  You are a super-hero in the year 2222 and you are faced with this great challenge: starting from your home planet Ilop you must try to reach Acinhet or else your planet will be destroyed by evil green little monsters. To do this you are given a map of the universe: there are N planets and M inter-planetary connections ( bidirectional ) that bind these planets. Each connection requires a certain time and a certain amount of fuel in order for you to cover the connection from one planet to another. The total time spent going from one planet to another is obtained by multiplying the time past to cover each connection between all the planets you go through. There are some "key planets", that allow you to refuel if you arrive on those certain "key planets". A "key planet" is the planet with the property that if it disappears the road between at least two planets would be lost.(In the example posted below with the input/output files such a "key planet" is 2 because without it the road to 7 would be lost) When you start your mission you are given the possibility of choosing between K ships each with its own maximum fuel capacity. The goal is to find the SHORTEST TIME CONSUMING path but also choose the ship with the minimum fuel capacity that can cover that shortest path(this means that if more ships can cover the shortest path you choose the one with the minimum fuel capacity). Because the minimum time can be a rather large number (over long long int) you are asked to provide only the last 6 digits of the number. For a better understanding of the task, here is an example of input/output files: INPUT: mission.in 7 8 6 1 4 6 5 9 8 7 10 1 2 7 8 1 4 14 9 1 5 3 1 2 3 1 2 2 7 7 1 3 4 2 2 4 6 4 1 5 6 3 7 On the first line (in order): N M K On the second line :the number for the starting planet and the finishing planet On the third line :K numbers that represent the capacities of the ships you can choose from Then you have M lines, all of them have the same structure: Xi Yi Ti Fi-which means that there is a connection between Xi and Yi and you can cover the distance from Xi to Yi in Ti time and with a Fi fuel consumption. OUTPUT:mission.out 000014 8 1 2 3 4 On the first line:the minimum time and fuel consumption; On the second line :the path Restrictions: 2 = N = 1 000 1 = M = 30 000 1 = K = 10 000 Any suggestions or ideas of how this problem might be solved would be most welcomed.

  Read the article

• SQL SERVER – Finding Shortest Distance between Two Shapes using Spatial Data Classes – Ramsetu or Adam’s Bridge

  - by pinaldave

  Recently I was reading excellent blog post by Lenni Lobel on Spatial Database. He has written very interesting function ShortestLineTo in Spatial Data Classes. I really loved this new feature of the finding shortest distance between two shapes in SQL Server. Following is the example which is same as Lenni talk on his blog article . DECLARE @Shape1 geometry = 'POLYGON ((-20 -30, -3 -26, 14 -28, 20 -40, -20 -30))' DECLARE @Shape2 geometry = 'POLYGON ((-18 -20, 0 -10, 4 -12, 10 -20, 2 -22, -18 -20))' SELECT @Shape1 UNION ALL SELECT @Shape2 UNION ALL SELECT @Shape1.ShortestLineTo(@Shape2).STBuffer(.25) GO When you run this script SQL Server finds out the shortest distance between two shapes and draws the line. We are using STBuffer so we can see the connecting line clearly. Now let us modify one of the object and then we see how the connecting shortest line works. DECLARE @Shape1 geometry = 'POLYGON ((-20 -30, -3 -30, 14 -28, 20 -40, -20 -30))' DECLARE @Shape2 geometry = 'POLYGON ((-18 -20, 0 -10, 4 -12, 10 -20, 2 -22, -18 -20))' SELECT @Shape1 UNION ALL SELECT @Shape2 UNION ALL SELECT @Shape1.ShortestLineTo(@Shape2).STBuffer(.25) GO Now once again let us modify one of the script and see how the shortest line to works. DECLARE @Shape1 geometry = 'POLYGON ((-20 -30, -3 -30, 14 -28, 20 -40, -20 -30))' DECLARE @Shape2 geometry = 'POLYGON ((-18 -20, 0 -10, 4 -12, 10 -20, 2 -18, -18 -20))' SELECT @Shape1 UNION ALL SELECT @Shape2 UNION ALL SELECT @Shape1.ShortestLineTo(@Shape2).STBuffer(.25) SELECT @Shape1.STDistance(@Shape2) GO You can see as the objects are changing the shortest lines are moving at appropriate place. I think even though this is very small feature this is really cool know. While I was working on this example, I suddenly thought about distance between Sri Lanka and India. The distance is very short infect it is less than 30 km by sea. I decided to map India and Sri Lanka using spatial data classes. To my surprise the plotted shortest line is the same as Adam’s Bridge or Ramsetu. Adam’s Bridge starts as chain of shoals from the Dhanushkodi tip of India’s Pamban Island and ends at Sri Lanka’s Mannar Island. Geological evidence suggests that this bridge is a former land connection between India and Sri Lanka. Reference: Pinal Dave (http://blog.sqlauthority.com) Filed under: PostADay, SQL, SQL Authority, SQL Function, SQL Query, SQL Server, SQL Tips and Tricks, T SQL, Technology Tagged: Spatial Database, SQL Spatial

  Read the article

• Find Shortest element in Array

  - by Ani

  I have a Array string[] names = { "Jim Rand", "Barry Williams", "Nicole Dyne", "Peter Levitt", "Jane Jones", "Cathy Hortings"}; Is there any way to find which is the shortest(Length wise) element in this array and then store rest of elements in a different array. Thanks, Ani

  Read the article

• Efficiently finding the shortest path in large graphs

  - by Björn Lindqvist

  I'm looking to find a way to in real-time find the shortest path between nodes in a huge graph. It has hundreds of thousands of vertices and millions of edges. I know this question has been asked before and I guess the answer is to use a breadth-first search, but I'm more interested in to know what software you can use to implement it. For example, it would be totally perfect if it already exist a library (with python bindings!) for performing bfs in undirected graphs.

  Read the article

• Shortest-path algorithms which use a space-time tradeoff?

  - by Chris Mounce

  I need to find shortest paths in an unweighted, undirected graph. There are algorithms which can find a shortest path between two nodes, but this can take time. There are also algorithms for computing shortest paths for all pairs of nodes in the graph, but storing such a lookup table would take lots of disk space. What I'm wondering: Is there an algorithm which offers a space-time tradeoff that's somewhere between these two extremes? In other words, is there a way to speed up a shortest-path search, while using less disk space than would be occupied by an all-pairs shortest-path table? I know there are ways to efficiently store lookup tables for this problem, and I already have a couple of ideas for speeding up shortest-path searches using precomputed data. But I don't want to reinvent the wheel if there's already some established algorithm that solves this problem.

  Read the article

• shortest path search in a map represented as 2d shapes

  - by joe_shmoe

  Hi, I have a small library of a few shortest path search algorithms. They were developed for simple undirected graphs (the normal representation - vertices and edges). Now I'd like to somehow apply them on a bit different scenario - where the maps are represented as 2-dimensional shapes, connected by shared edges (edges of the polygons, that is). In this scenario, the search can start/end either at a map object or some point (x,y). What would be the best approach? Try to apply the algorithms onto shapes? or try to extract a 'normal' graph out of the shapes (I have preprocessing time available)? Any advice would be much appreciated, as I'm really not sure which way to go, and I don't have enough time (and skill) to explore many options... Thanks a lot

  Read the article

• Shortest acyclic path on directed cyclic graph with negative weights/cycles

  - by Janathan

  I have a directed graph which has cycles. All edges are weighted, and the weights can be negative. There can be negative cycles. I want to find a path from s to t, which minimizes the total weight on the path. Sure, it can go to negative infinity when negative cycles exist. But what if I disallow cycles in the path (not in the original graph)? That is, once the path leaves a node, it can not enter the node again. This surely avoids the negative infinity problem, but surprisingly no known algorithm is found by a search on Google. The closest is Floyd–Warshall algorithm, but it does not allow negative cycles. Thanks a lot in advance. Edit: I may have generalized my original problem too much. Indeed, I am given a cyclic directed graph with nonnegative edge weights. But in addition, each node has a positive reward too. I want to find a simple path which minimizes (sum of edge weights on the path) - (sum of node rewards covered by the path). This can be surely converted to the question that I posted, but some structure is lost. And some hint from submodular analysis suggests this motivating problem is not NP-hard. Thanks a lot

  Read the article

• Finding the shortest path through a digraph that visits all nodes

  - by Boluc Papuccuoglu

  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 directed, meaning that being able to travel from node A to node B does not mean one can travel from node B to node A. All distances between nodes are equal. I was able to code a brute force search that found a path of only 27 nodes when I had 27 nodes and each node had a connection to 2 or 1 other node. However, the actual problem that I am trying to solve consists of 256 nodes, with each node connecting to either 4 or 3 other nodes. The brute force algorithm that solved the 27 node graph can produce a 415 node solution (not optimal) within a few seconds, but using the processing power I have at my disposal takes about 6 hours to arrive at a 402 node solution. What approach should I use to arrive at a solution that I can be certain is the optimal one? For example, use an optimizer algorithm to shorten a non-optimal solution? Or somehow adopt a brute force search that discards paths that are not optimal? EDIT: (Copying a comment to an answer here to better clarify the question) To clarify, I am not saying that there is a Hamiltonian path and I need to find it, I am trying to find the shortest path in the 256 node graph that visits each node AT LEAST once. With the 27 node run, I was able to find a Hamiltonian path, which assured me that it was an optimal solution. I want to find a solution for the 256 node graph which is the shortest.

  Read the article

• SQL SERVER – Solution – 2 T-SQL Puzzles – Display Star and Shortest Code to Display 1

  - by pinaldave

  Earlier on this blog we had asked two puzzles. The response from all of you is nothing but Amazing. I have received 350+ responses. Many are valid and many were indeed something I had not thought about it. I strongly suggest you read all the puzzles and their answers here - trust me if you start reading the comments you will not stop till you read every single comment. Seriously trust me on it. Personally I have learned a lot from it. Let us recap the puzzles here quickly. Puzzle 1: Why following code when executed in SSMS displays result as a * (Star)? SELECT CAST(634 AS VARCHAR(2)) Puzzle 2: Write the shortest code that produces results as 1 without using any numbers in the select statement. Bonus Q: How many different Operating System (OS) NuoDB support? As I mentioned earlier the participation was nothing but Amazing. I will write about the winners and the best answers in short time. Meanwhile I will give to the point answers to above puzzles. Solution 1: When you convert character or binary expressions (char, nchar, nvarchar, varchar,binary, or varbinary) to an expression of a different data type, data can be truncated, only partially displayed, or an error is returned because the result is too short to display. Conversions to char, varchar, nchar, nvarchar, binary, and varbinary are truncated, except for the conversions shown in the following table. Reference of the text and table from MSDN. Solution 2: The shortest code to produce answer 1 : SELECT EXP($) or SELECT COS($) or SELECT DAY($) When SELECT $ it gives us the result as 0.00 and the EXP of the same is 1. I believe it is pretty neat. There were plenty other answers but this was the shortest. Another shorter answer would be PRINT EXP($) but no one has proposed that as in original Question I have explicitly mentioned SELECT in the original question. Bonus Answer: 5 OS: Windows, MacOS, Linux, Solaris, Joyent SmartOS Reference Please do read every single comment here. Do leave a comment which one do you think is the best comment out of all the comments. Meanwhile if there is a better solution and I have missed it do let me know as we still have time to correct it. I will be selecting the winner before the weekend as I am going through each and every of 350 comment. I will be selecting the best comments along with the winning comment. If our selection matches – one of you may still win something cool.  Reference: Pinal Dave (http://blog.SQLAuthority.com) Filed under: PostADay, SQL, SQL Authority, SQL Puzzle, SQL Query, SQL Server, SQL Tips and Tricks, SQLServer, T SQL, Technology Tagged: NuoDB

  Read the article

• Looking for an algorithm to connect dots - shortest route

  - by e4ch

  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 (usually 2-5, theoretical limit is 1-26). I have exactly one starting point and about 30 exit points (probably all of the exit points are connected to each other). Many of these 3200 points are probably not connected to neither start nor end point in any way, like a separate net, but all points are connected to at least one other point. I need to find the shortest number of hops to go from entry to exit. There is no distance between the points (unlike the road or train routing problem), just the number of hops counts. I need to find all solutions with the shortest number of hops, and not just one solution, but all. And potentially also solutions with one more hop etc. I expect to have a solution with about 30-50 hops to go from start to exit. I already tried: 1) randomly trying possibilities and just starting over when the count was bigger than a previous solution. I got first solution with 3500 hops, then it got down to about 97 after some minutes, but looking at the solutions I saw problems like unnecessary loops and stuff, so I tried to optimize a bit (like not going back where it came from etc.). More optimizations are possible, but this random thing doesn't find all best solutions or takes too long. 2) Recursively run through all ways from start (chess-problem-like) and breaking the try when it reached a previous point. This was looping at about a length of 120 nodes, so it tries chains that are (probably) by far too long. If we calculate 4 possibilities and 120 nodes, we're reaching 1.7E72 possibilities, which is not possible to calculate through. This is called Depth-first search (DFS) as I found out in the meantime. Maybe I should try Breadth-first search by adding some queue? The connections between the points are actually moves you can make in the game and the points are how the game looks like after you made the move. What would be the algorithm to use for this problem? I'm using C#.NET, but the language shouldn't matter.

  Read the article

• Finding shortest path on a hexagonal grid

  - by Timothy Mayes

  I'm writing a turn based game that has some simulation elements. One task i'm hung up on currently is with path finding. What I want to do is, each turn, move an ai adventurer one tile closer to his target using his current x,y and his target x,y. In trying to figure this out myself I can determine 4 directions no problem by using dx = currentX - targetY dy = currentY - targetY but I'm not sure how to determine which of the 6 directions is actually the "best" or "shortest" route. For example the way its setup currently I use East, West, NE, NW, SE, SW but to get to the NE tile i move East then NW instead of just moving NW. I hope this wasn't all rambling. Even just a link or two to get me started would be nice. Most of the info i've found is on drawing the grids and groking the wierd coordinate system needed. Thanks in advance Tim

  Read the article

• The shortest licenses

  - by Darek Nedza

  What are the shortest licenses with aims for programmers/code. I have found only MIT that is page-long. What are other licenses that have approximately the same length or even shorter? Edit: Ok, length is not only criteria(I haven't expected one-line licenses, I have understaminate you people). I need easy to read and short licenses. It is meant for people who want to use my code not for lawyers who want to read long licenses. I am creating small codes to use by most people probably free of charge. I don't want useless information to be required, for example: what is X(for example: what is software, source code etc.) very specific information(for example: you can use it shop, opera, school... free of charge; but instead "use it everywhere but don't take money" Depending on type of code I would like to allow/disallow commercial usage.

  Read the article

• How to optimize Dijkstra algorithm for a single shortest path between 2 nodes?

  - by Nazgulled

  Hi, I was trying to understand this implementation in C of the Dijkstra algorithm and at the same time modify it so that only the shortest path between 2 specific nodes (source and destination) is found. However, I don't know exactly what do to. The way I see it, there's nothing much to do, I can't seem to change d[] or prev[] cause those arrays aggregate some important data for the shortest path calculation. The only thing I can think of is stopping the algorithm when the path is found, that is, break the cycle when mini = destination when it's being marked as visited. Is there anything else I could do to make it better or is that enough? P.S: I just noticed that the for loops start at 1 until <=, why can't it start at 0 and go until <?

  Read the article

• finding the total number of distinct shortest paths between 2 nodes in undirected weighted graph in linear time?

  - by logan

  I was wondering, that if there is a weighted graph G(V,E), and I need to find a single shortest path between any two vertices S and T in it then I could have used the Dijkstras algorithm. but I am not sure how this can be done when we need to find all the distinct shortest paths from S to T. Is it solvable on O(n) time? I had one more question like if we assume that the weights of the edges in the graph can assume values only in certain range lets say 1 <=w(e)<=2 will this effect the time complexity?

  Read the article

• Is there any library in R to work with graphs (find shortest path and so on)?

  - by Ivri

  Hi! I know that R is statistical pkg, but probably there is library to work with graphs and find shortest path btw 2 nodes. Thank you

  Read the article

• How would you write a program to find the shortest pangram in a list of words?

  - by jonathanasdf

  Given a list of words which contains the letters a-z at least once, how would you write a program to find the shortest pangram counted by number of characters (not counting spaces) as a combination of the words? Since I am not sure whether short answers exist, this is not code golf, but rather just a discussion of how you would approach this. However, if you think you can manage to write a short program that would do this, then go ahead, and this might turn into code golf :)

  Read the article

• Algorithm for Shortest Job First with Preemption

  - by Shray

  I want to implement a shortest job first routine using C# or C++. Priority of Jobs are based on their processing time. Jobs are processed using a binary (min) heap. There are three types of jobs. Type 1 is when jobs come in between every 4-6 seconds, with processing times between 4-6. Type 2 job comes in between 8-12 seconds, with processing times between 8-12. Type 3 job comes in between 24-26 seconds, with processing times between 14-16. So far, I have written the binary heap functionality, but Im kinda confused on how to start processing spawn and also the processor. #include <iostream> #include <stdlib.h> #include <time.h> using namespace std; int timecounting = 20; struct process{ int atime; int ptime; int type; }; class pque{ private: int count; public: process pheap[100]; process type1[100]; process type2[100]; process type3[100]; process type4[100]; pque(){ count = 0; } void swap(int a, int b){ process tempa = pheap[a]; process tempb = pheap[b]; pheap[b] = tempa; pheap[a] = tempb; } void add(process c){ int current; count++; pheap[count] = c; if(count > 0){ current = count; while(pheap[count/2].ptime > pheap[current].ptime){ swap(current/2, current); current = current/2; } } } void remove(){ process temp = pheap[1]; // saves process to temporary pheap[1] = pheap[count]; //takes last process in heap, and puts it at the root int n = 1; int leftchild = 2*n; int rightchild = 2*n + 1; while(leftchild < count && rightchild < count) { if(pheap[leftchild].ptime > pheap[rightchild].ptime) { if(pheap[leftchild].ptime > pheap[n].ptime) { swap(leftchild, n); n = leftchild; int leftchild = 2*n; int rightchild = 2*n + 1; } } else { if(pheap[rightchild].ptime > pheap[n].ptime) { swap(rightchild, n); n = rightchild; int leftchild = 2*n; int rightchild = 2*n + 1; } } } } void spawn1(){ process p; process p1; p1.atime = 0; int i = 0; srand(time(NULL)); while(i < timecounting) { p.atime = rand()%3 + 4 + p1.atime; p.ptime = rand()%5 + 1; p1.atime = p.atime; p.type = 1; type1[i+1] = p; i++; } } void spawn2(){ process p; process p1; p1.atime = 0; srand(time(NULL)); int i = 0; while(i < timecounting) { p.atime = rand()%3 + 9 + p1.atime; p.ptime = rand()%5 + 6; p1.atime = p.atime; p.type = 2; type2[i+1] = p; i++; } } void spawn3(){ process p; process p1; p1.atime = 0; srand(time(NULL)); int i = 0; while(i < timecounting) { p.atime = rand()%3 + 25 + p1.atime; p.ptime = rand()%5 + 11; p1.atime = p.atime; p.type = 3; type3[i+1] = p; i++; } } void spawn4(){ process p; process p1; p1.atime = 0; srand(time(NULL)); int i = 0; while(i < timecounting) { p.atime = rand()%6 + 30 + p1.atime; p.ptime = rand()%5 + 8; p1.atime = p.atime; p.type = 4; type4[i+1] = p; i++; } } void processor() { process p; process p1; p1.atime = 0; int n = 1; int n1 = 1; int n2 = 1; for(int i = 0; i<timecounting;i++) { if(type1[n].atime == i) { add(type1[n]); n++; } if(type2[n1].atime == i) { add(type1[n1]); n1++; } if(type3[n2].atime == i) { add(type1[n2]); n2++; } /* if(pheap[1].atime <= i) { while(pheap[1].atime != 0){ pheap[1].atime--; i++; } remove(); }*/ } } };

  Read the article

• Finding the shortest path between two points on a grid, using Haskell.

  - by esperantist

  This is a problem that I can easily enough solve in a non-functional manner. But solving it in Haskell is giving me big problems. Me being inexperienced when it comes to functional programming is surely a reason. The problem: I have a 2D field divided into rectangles of equal size. A simple grid. Some rectangles are empty space (and can be passed through) while others are impassable. Given a starting rectangle A and a destination rectangle B, how would I calculate the shortest path between the two? Movement is possible only vertically and horizontally, in steps a single rectangle large. How would I go about accomplishing this in Haskell? Code snippets certainly welcome, but also certainly not neccessary. And links to further resources also very welcome! Thanks!

  Read the article

1 2 3 4 5 6 7 8 9 10 11 12  | Next Page >