what is Dijkstra's algorithm?
139974
Dijkstra's algorithm, named after its discoverer, Dutch computer scientist Edsger Dijkstra, is an algorithm that solves the single-source shortest path problem for a directed graph with nonnegative edge weights.\n\nFor example, if the vertices of the graph represent cities and edge weights represent driving distances between pairs of cities connected by a direct road, Dijkstra's algorithm can be used to find the shortest route between two cities.\n\nThe input of the algorithm consists of a weighted directed graph G and a source vertex s in G. We will denote V the set of all vertices in the graph G. Each edge of the graph is an ordered pair of vertices (u,v) representing a connection from vertex u to vertex v. The set of all edges is denoted E. Weights of edges are given by a weight function w: E → [0, ∞]; therefore w(u,v) is the non-negative cost of moving from vertex u to vertex v. The cost of an edge can be thought of as (a generalization of) the distance between those two vertices. The cost of a path between two vertices is the sum of costs of the edges in that path. For a given pair of vertices s and t in V, the algorithm finds the path from s to t with lowest cost (i.e. the shortest path). It can also be used for finding costs of shortest paths from a single vertex s to all other vertices in the graph.\n\nhttp://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
67339
See the explanation in the Wikipedia here:\n\nhttp://en.wikipedia.org/wiki/Methods_of_computing_square_roots\n\nScroll down the the section marked "An exact long-division-like algorithm".
19142
Its based on Artificial Neural Networks, which are programmatical methods of trying to duplicate the activity of the human brain. It comprises of a learning stage, where the paths to different methods are chalked out. Then, when the input comes in, the program tries to track the path of the successive answers to ones that match the user's input closest (one method of achieving this is finding the least difference between each pair of input and entry in the database). This is done stage-wise, until a good guess is made on the possible solution to the user's responses.
526760
go to the source - The Art of Computer Programming by Donald Knuth.  It is the bible of data structures.
189552
If I'm understanding what you are looking for, a DAG-based algorithm would basically be a "state machine" with no cyclical states -- in other words, once you left a state, there was no way in the graph to return to that state.\n\nIf you want a very, VERY ugly version of one, consider a recursive function controlled by a switch statement. Each vertex does something that ends in a decision point which will change the state to the next vertex -- or exit once a sink is encountered. You could represent any DAG this way, most likely...and as long as you entered the function the initial time at a source, you would end up at the appropriate sink.\n\nTry it with the DAG that is on the Wikipedia diagram below.
460132
Prolog or Lisp. Machine learning\nMore detail please.\nI'm more for Java.\nBut most likely you are looking for the toolkit From MATLAB(tm) the first link.
218696
There may be some good theory on this topic, but\nI'd like to point out one obvious solution and\none possibly-special-case solution.\n\nFirst, given a graph, if you have the ability to \ntraverse the entire graph and "mark" each node as\nyou visit it, then if you ever run into a marked\nnode, then there is a cycle.  The most obvious way\nto mark a node is to store a flag in it, but it\nis also possible to build a separate data structure\nto keep track of each node (ie. a hash table \nindexed by node address or something like that.)\n\nAnother trick I've seen used on lists, but *might* be\ngeneralized to some more-complicated graphs, is the\nidea of a follow-pointer.  In the case of a list,\nthe "follow pointer" traverses one list link\nfor every *two* that the real traversal covers.\nIf there is a loop in the list, eventually the\n"lead" pointer will wrap around and catch up\nto the "follow" pointer.  Thus, you know that\nthere's a cycle if the two pointers ever refer\nto the same node.
1097839
1.algorithm: A computable set of steps to achieve a desired result. \n\n\n2.Data struture:A conceptual unity or an organized information such as name & address of a person, tree, automatic telephone operating sytem.\n\n3.Pseudocode:Pseudocode is a kind of structured english for describing algorithms. It allows the designer to focus on the logic of the algorithm without being distracted by details of language syntax\n\n4.Flow chart:A flowchart illustrates the steps in a process. By visualizing the process, a flowchart can quickly help identify bottlenecks or inefficiencies where the process can be streamlined or improved.
141533
I think you are asking about ALGORITHM:\nan algorithm is a logical recipe for performing some operation by the computer.
605529
A routing protocol which uses routing algorithms helps a router to send data packets to correct destination. When you write www.yahoo.com to the address bar of your browser and press enter, you make a request to yahoo.com but where the hell is that yahoo machine? \n\nFirst a DNS resolution occurs and your Internet Explorer learns yahoo machine's IP. Then send datas to the IP number. But then again how IP packets (data packets) find their way to yahoo? There must be some traffic polices - we call routers - that sends these data packets between themselves finally to destination. They are like stepping stones accross a river but there are lots of these stones and packets must cross the river via the shortest path to the otherside. So policemen - or stones - must know the next stone location on the path. \n\nFinally comes the routing protocols and their algorithms...  Routing protocols reveal routers (policeman, stepping stones, you name it), which way to the destination (the otherside of the river). To be precise which router is the next route to the destination, so that packets hopping one router to the other to be lasted on the destination : yahoo.com. Routing protocols uses some algorithms to make these decisions, and (at last) these algorithms are the ones you ask.\n\nBut you must not mix routing protocols with the routed protocols. The sending of the actual data is done by routed protocols, but the learning of the way by router done via routing protocols... \n\nPopuler Routing Protocols : RIP, IGRP, BGP, OSPF (Open Shortest Path First, not "Obtain")\nPopuler Routed Protocols : IP, IPX\n\nI hope the links I gave helps.\nCheers.
513189
Neville's algorithm is an algorithm used to construct unique, interpolating polynomials. It uses n + 1 points to construct polynomials of degree n.\n\nIt is similar to Aitken's algorithm, which is nowadays not used.
153362
You need to look into "balanced trees". Check out any good algorithms book - my personal favourite is "Algorithms" by Robert Sedgewick.\n\nHope this helps!\n\n-----------\nEdit:\nBinary tree will not work as they have O(n) worst cases for maximum, minimum, search, insert and delete. These pathological cases are avoided by the rebalancing techniques used in balanced trees.
772919
Imagine that a travelling salesman has to hit, say, 100 cities in the USA, and he knows road distances between them, what's the minimum distance he has to travel to do all of them and come back home?  There are numerous variations on this problem, but this kind of a problem usually defies mathematical analysis.  It's called a "NP-hard' problem, which is a measure of the time it takes a computer to determine the optimum path.
890951
http://en.wikipedia.org/wiki/Routing
104358
MAZE NAVIGATION ALGORITHM\n\nPart 1\n\n    A guaranteed way to to solve a maze is to stick to a wall and always try to turn one direction or the other.  It is not the most efficient way but it works all the time.  This is how the Boe-Bot solves mazes.  It hugs the left wall.  IR sensors are mounted on the left and front sides of the robot.  It begins the maze with a forward movement.  After that it checks the left IR.  If left is open, it turns left, moves forward, and repeats the process.  If left is closed, the robot checks the front.  If front is open, the robot moves forward and repeats the process.  If the front is also closed, the  robot turns right.  It then checks the front IR sensor to determine if the new front is open.  If its open, the robot moves forward and repeats the process.  If it is closed, the robot again turns right and moves forward (the way it just came) and repeats the process.  The flow chart summarizes all these instructions.  Each time the robot makes a movement (forward, left, or right) it records a F,L, or R to a memory block in the EEPROM by using the WRITE function in Stamp BASIC.  The variable 'total_moves' is incremented each time a movement is written.  \n\n    The forward, left, and right subroutines use the PULSOUT function to move the servos.  The pulsout variables for each servo (eg. 699, 879) are not set in stone.  They have been changed numerous times and will probably need to be played with more.   We determined them partly by experiment and largely by trial and error.  The results of those experiments are also published in this site.  \n\n    At the beginning of the forward subroutine is the BUTTON function.  Each time through this subroutine, the programs checks to see if the button has been depressed.  If it has not, the program continues.  If the button has been pressed, control is moved to the find_RR subroutine.\n\nPart 2\n\n    When the program enters part 2, the robot has already left the maze and the button has been pressed.  It enters the find_RR subroutine and first pauses for 10 seconds so the robot can be repositioned at the starting point to re-do the maze.  Find_RR is a superfluous piece of code that originated from poor planning.  It reads in the movement from each memory block and the following memory block (blocks n and n+1) and compares them to each other.  If it detects a R,R combo, it replaces the first R with an A.  It then copies each movement into the previous one.  For example, it would change a FFRRFLF to a FFAFLF.  Each time it finds an RR combo and replaces it with an A, all the code following the last R must be adjusted. Therefore, the 'total_moves' variable is reduced by 1 each time RR is detected.  The write_A subroutine handles that task.  If no RR combo is found (they've all been switched) control moves to the find_A subroutine.\n\n    Find_A searches each memory block for the 'A' movement.  If no 'A' is found, control moves to the done subroutine.  However, this will only occur after all the 'A' have been dealt with.  When an 'A' is found, the memory location is stored in variable 'counter' and control goes to subroutine surround_A.  The purpose of surround_A is to determine all of the movements before and after the 'A' that need to be ignored for successful completion of the maze.  \n\n    After the robot completes the maze for the first time, and changes the 'RR' to 'A' the code will something like:\n\n        F F F L F A F R F F L F  this is for the hypothetical situation shown here:\n\n\n\n To eliminate the unwanted code, the pairs of movements surrounding A are examined and compared to the green, blue and purple patterns.\n\nF                F                F            L                F            A                F                R                F                F            L            F\n\n0                1                 2            3                4
447556
Look up "quicksort".\n\nIt fits very naturally into a recursive implementation\nand is also a very efficient sorting algorithm.\n\nI've included a link to the Solaris source for quicksort.\nIt is written in C (rather than C++).  It is somewhat\ncomplicated because it optimizes the sorting of\nshort sequences by switching to an insertion sort.\nHowever, you could implement a simpler version which\nran quicksort all the way to completion.
175453
Input Description: A graph G = (V,E) with weighted edges.\n\nProblem: The subset of E of G of minimum weight which forms a tree on V.\n\nExcerpt from The Algorithm Design Manual: The minimum spanning tree (MST) of a graph defines the cheapest subset of edges that keeps the graph in one connected component. Telephone companies are particularly interested in minimum spanning trees, because the minimum spanning tree of a set of sites defines the wiring scheme that connects the sites using as little wire as possible. It is the mother of all network design problems. Minimum spanning trees prove important for several reasons:\n\n    * They can be computed quickly and easily, and they create a sparse subgraph that reflects a lot about the original graph.\n    * They provide a way to identify clusters in sets of points. Deleting the long edges from a minimum spanning tree leaves connected components that define natural clusters in the data set, as shown in the output figure above.\n    * They can be used to give approximate solutions to hard problems such as Steiner tree and traveling salesman.\n    * As an educational tool, minimum spanning tree algorithms provide graphic evidence that greedy algorithms can give provably optimal solutions.