Faster access than browser!
62 relations: A* search algorithm, Abstract machine, Andrew V. Goldberg, Bellman–Ford algorithm, Bidirectional search, Binary heap, Breadth-first search, Canadian traveller problem, Computational geometry, Computer network, Consistent heuristic, Contraction hierarchies, Dense graph, Dijkstra's algorithm, Discrete Applied Mathematics, Discrete optimization, Dynamic programming, Euclidean shortest path, Fibonacci heap, Flow network, Floyd–Warshall algorithm, Google Maps, Graph (discrete mathematics), Graph theory, IEEE 802.1aq, Information algebra, Institute of Electrical and Electronics Engineers, Johnson's algorithm, Journal of Automata, Languages and Combinatorics, Journal of Computer and System Sciences, Linear programming, Longest path problem, MapQuest, Min-plus matrix multiplication, Mixed graph, NP-completeness, Operations research, P versus NP problem, Path (graph theory), Pathfinding, Reduced cost, Reptation, Robotics, Rubik's Cube, Seidel's algorithm, Semiring, Sequence, Shortest-path tree, Six degrees of separation, Stochastic optimization, ..., Symposium on Theory of Computing, Telecommunications network, Time complexity, Transport, Travelling salesman problem, Triangle inequality, Valuation (algebra), Vertex (graph theory), Very-large-scale integration, Viterbi algorithm, Web mapping, Widest path problem. Expand index (12 more) »
A* search algorithm
In computer science, A* (pronounced as "A star") is a computer algorithm that is widely used in pathfinding and graph traversal, which is the process of plotting an efficiently directed path between multiple points, called "nodes".
New!!: Shortest path problem and A* search algorithm · See more »
Abstract machine
An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in automata theory.
New!!: Shortest path problem and Abstract machine · See more »
Andrew V. Goldberg
Andrew Vladislav Goldberg (born 1960) is an American computer scientist working primarily on design, analysis, and experimental evaluation of algorithms.
New!!: Shortest path problem and Andrew V. Goldberg · See more »
Bellman–Ford algorithm
The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph.
New!!: Shortest path problem and Bellman–Ford algorithm · See more »
Bidirectional search
Bidirectional search is a graph search algorithm that finds a shortest path from an initial vertex to a goal vertex in a directed graph.
New!!: Shortest path problem and Bidirectional search · See more »
Binary heap
A binary heap is a heap data structure that takes the form of a binary tree.
New!!: Shortest path problem and Binary heap · See more »
Breadth-first search
Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures.
New!!: Shortest path problem and Breadth-first search · See more »
Canadian traveller problem
In computer science and graph theory, the Canadian traveller problem (CTP) is a generalization of the shortest path problem to graphs that are partially observable.
New!!: Shortest path problem and Canadian traveller problem · See more »
Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry.
New!!: Shortest path problem and Computational geometry · See more »
Computer network
A computer network, or data network, is a digital telecommunications network which allows nodes to share resources.
New!!: Shortest path problem and Computer network · See more »
Consistent heuristic
In the study of path-finding problems in artificial intelligence, a heuristic function is said to be consistent, or monotone, if its estimate is always less than or equal to the estimated distance from any neighboring vertex to the goal, plus the step cost of reaching that neighbor.
New!!: Shortest path problem and Consistent heuristic · See more »
Contraction hierarchies
In applied mathematics, the method of contraction hierarchies is a technique to speed up shortest-path routing by first creating precomputed "contracted" versions of the connection graph.
New!!: Shortest path problem and Contraction hierarchies · See more »
Dense graph
In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges.
New!!: Shortest path problem and Dense graph · See more »
Dijkstra's algorithm
Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks.
New!!: Shortest path problem and Dijkstra's algorithm · See more »
Discrete Applied Mathematics
Discrete Applied Mathematics is a peer-reviewed academic journal in mathematics, published by Elsevier.
New!!: Shortest path problem and Discrete Applied Mathematics · See more »
Discrete optimization
Discrete optimization is a branch of optimization in applied mathematics and computer science.
New!!: Shortest path problem and Discrete optimization · See more »
Dynamic programming
Dynamic programming is both a mathematical optimization method and a computer programming method.
New!!: Shortest path problem and Dynamic programming · See more »
Euclidean shortest path
The Euclidean shortest path problem is a problem in computational geometry: given a set of polyhedral obstacles in a Euclidean space, and two points, find the shortest path between the points that does not intersect any of the obstacles.
New!!: Shortest path problem and Euclidean shortest path · See more »
Fibonacci heap
In computer science, a Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees.
New!!: Shortest path problem and Fibonacci heap · See more »
Flow network
In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow.
New!!: Shortest path problem and Flow network · See more »
Floyd–Warshall algorithm
In computer science, the Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles).
New!!: Shortest path problem and Floyd–Warshall algorithm · See more »
Google Maps
Google Maps is a web mapping service developed by Google.
New!!: Shortest path problem and Google Maps · See more »
Graph (discrete mathematics)
In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related".
New!!: Shortest path problem and Graph (discrete mathematics) · See more »
Graph theory
In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.
New!!: Shortest path problem and Graph theory · See more »
IEEE 802.1aq
Shortest Path Bridging (SPB), specified in the IEEE 802.1aq standard, is a computer networking technology intended to simplify the creation and configuration of networks, while enabling multipath routing.
New!!: Shortest path problem and IEEE 802.1aq · See more »
Information algebra
The term "information algebra" refers to mathematical techniques of information processing.
New!!: Shortest path problem and Information algebra · See more »
Institute of Electrical and Electronics Engineers
The Institute of Electrical and Electronics Engineers (IEEE) is a professional association with its corporate office in New York City and its operations center in Piscataway, New Jersey.
New!!: Shortest path problem and Institute of Electrical and Electronics Engineers · See more »
Johnson's algorithm
Johnson's algorithm is a way to find the shortest paths between all pairs of vertices in a sparse, edge-weighted, directed graph.
New!!: Shortest path problem and Johnson's algorithm · See more »
Journal of Automata, Languages and Combinatorics
The Journal of Automata, Languages and Combinatorics is a peer-reviewed scientific journal of computer science, edited by Jürgen Dassow.
New!!: Shortest path problem and Journal of Automata, Languages and Combinatorics · See more »
Journal of Computer and System Sciences
The Journal of Computer and System Sciences (JCSS) is a peer-reviewed scientific journal in the field of computer science.
New!!: Shortest path problem and Journal of Computer and System Sciences · See more »
Linear programming
Linear programming (LP, also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships.
New!!: Shortest path problem and Linear programming · See more »
Longest path problem
In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph.
New!!: Shortest path problem and Longest path problem · See more »
MapQuest
MapQuest (stylized as mapquest) is an American free online web mapping service owned by Verizon.
New!!: Shortest path problem and MapQuest · See more »
Min-plus matrix multiplication
Min-plus matrix multiplication, also known as the distance product, is an operation on matrices.
New!!: Shortest path problem and Min-plus matrix multiplication · See more »
Mixed graph
A mixed graph G.
New!!: Shortest path problem and Mixed graph · See more »
NP-completeness
In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes.
New!!: Shortest path problem and NP-completeness · See more »
Operations research
Operations research, or operational research in British usage, is a discipline that deals with the application of advanced analytical methods to help make better decisions.
New!!: Shortest path problem and Operations research · See more »
P versus NP problem
The P versus NP problem is a major unsolved problem in computer science.
New!!: Shortest path problem and P versus NP problem · See more »
Path (graph theory)
In graph theory, a path in a graph is a finite or infinite sequence of edges which connect a sequence of vertices which, by most definitions, are all distinct from one another.
New!!: Shortest path problem and Path (graph theory) · See more »
Pathfinding
Pathfinding or pathing is the plotting, by a computer application, of the shortest route between two points.
New!!: Shortest path problem and Pathfinding · See more »
Reduced cost
In linear programming, reduced cost, or opportunity cost, is the amount by which an objective function coefficient would have to improve (so increase for maximization problem, decrease for minimization problem) before it would be possible for a corresponding variable to assume a positive value in the optimal solution.
New!!: Shortest path problem and Reduced cost · See more »
Reptation
Reptation is the thermal motion of very long linear, entangled macromolecules in polymer melts or concentrated polymer solutions.
New!!: Shortest path problem and Reptation · See more »
Robotics
Robotics is an interdisciplinary branch of engineering and science that includes mechanical engineering, electronics engineering, computer science, and others.
New!!: Shortest path problem and Robotics · See more »
Rubik's Cube
Rubik's Cube is a 3-D combination puzzle invented in 1974 by Hungarian sculptor and professor of architecture Ernő Rubik.
New!!: Shortest path problem and Rubik's Cube · See more »
Seidel's algorithm
Seidel's algorithm is an algorithm designed by Raimund Seidel in 1992 for the all-pairs-shortest-path problem for undirected, unweighted, connected graphs.
New!!: Shortest path problem and Seidel's algorithm · See more »
Semiring
In abstract algebra, a semiring is an algebraic structure similar to a ring, but without the requirement that each element must have an additive inverse.
New!!: Shortest path problem and Semiring · See more »
Sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed.
New!!: Shortest path problem and Sequence · See more »
Shortest-path tree
Given a connected, undirected graph G, a shortest-path tree rooted at vertex v is a spanning tree T of G, such that the path distance from root v to any other vertex u in T is the shortest path distance from v to u in G. In connected graphs where shortest paths are well-defined (i.e. where there are no negative-length cycles), we may construct a shortest-path tree using the following algorithm.
New!!: Shortest path problem and Shortest-path tree · See more »
Six degrees of separation
Six degrees of separation is the idea that all living things and everything else in the world are Six or fewer steps away from each other so that a chain of "a friend of a friend" statements can be made to connect any two people in a maximum of Six steps.
New!!: Shortest path problem and Six degrees of separation · See more »
Stochastic optimization
Stochastic optimization (SO) methods are optimization methods that generate and use random variables.
New!!: Shortest path problem and Stochastic optimization · See more »
Symposium on Theory of Computing
The Annual ACM Symposium on Theory of Computing (STOC) is an academic conference in the field of theoretical computer science.
New!!: Shortest path problem and Symposium on Theory of Computing · See more »
Telecommunications network
A telecommunications network is a collection of terminal nodes, links are connected so as to enable telecommunication between the terminals.
New!!: Shortest path problem and Telecommunications network · See more »
Time complexity
In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm.
New!!: Shortest path problem and Time complexity · See more »
Transport
Transport or transportation is the movement of humans, animals and goods from one location to another.
New!!: Shortest path problem and Transport · See more »
Travelling salesman problem
The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.
New!!: Shortest path problem and Travelling salesman problem · See more »
Triangle inequality
In mathematics, the triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side.
New!!: Shortest path problem and Triangle inequality · See more »
Valuation (algebra)
In algebra (in particular in algebraic geometry or algebraic number theory), a valuation is a function on a field that provides a measure of size or multiplicity of elements of the field.
New!!: Shortest path problem and Valuation (algebra) · See more »
Vertex (graph theory)
In mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of vertices), while a directed graph consists of a set of vertices and a set of arcs (ordered pairs of vertices).
New!!: Shortest path problem and Vertex (graph theory) · See more »
Very-large-scale integration
Very-large-scale integration (VLSI) is the process of creating an integrated circuit (IC) by combining hundreds of thousands of transistors or devices into a single chip.
New!!: Shortest path problem and Very-large-scale integration · See more »
Viterbi algorithm
The Viterbi algorithm is a dynamic programming algorithm for finding the most likely sequence of hidden states—called the Viterbi path—that results in a sequence of observed events, especially in the context of Markov information sources and hidden Markov models.
New!!: Shortest path problem and Viterbi algorithm · See more »
Web mapping
Web mapping is the process of using the maps delivered by geographic information systems (GIS) in World Wide Web.
New!!: Shortest path problem and Web mapping · See more »
Widest path problem
In graph algorithms, the widest path problem is the problem of finding a path between two designated vertices in a weighted graph, maximizing the weight of the minimum-weight edge in the path.
New!!: Shortest path problem and Widest path problem · See more »
Redirects here:
APSP, All pairs shortest path, All pairs shortest path problem, All-pairs shortest path, All-pairs shortest path problem, Apsp, DAG shortest paths, Negative cycle, Shortest Path Algorithms, Shortest Path Problem, Shortest path, Shortest path algorithm, Shortest path algorithms, Shortest path problems, Shortest path routing, Shortest paths, Shortest-distance problems, Shortest-path, Shortest-path algorithms, Shortest-path problem, Shortest-path problems, Shortest-path routing, Shortest-paths, Shortestpath, Shortestpath problem, Shortestpath problems, Shortestpaths, Single destination shortest path problem, Single destination shortest-path problem, Single destination shortestpath problem, Single source shortest path problem, Single source shortest-path problem, Single source shortestpath problem, Single-destination shortest path problem, Single-destination shortest-path problem, Single-destination shortestpath problem, Single-pair shortest-path problem, Single-source shortest path problem, Single-source shortest-path problem, Single-source shortest-paths algorithms for directed graphs with nonnegative weights, Single-source shortestpath problem, Singledestination shortest path problem, Singledestination shortest-path problem, Singledestination shortestpath problem, Singlesource shortest path problem, Singlesource shortest-path problem, Singlesource shortestpath problem, The Shortest Paths.
References
[1] https://en.wikipedia.org/wiki/Shortest_path_problem
