Shortest path problem

View this topic in
In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. (Wikipedia.org)






Conferences related to Shortest path problem

Back to Top

ICC 2021 - IEEE International Conference on Communications

IEEE ICC is one of the two flagship IEEE conferences in the field of communications; Montreal is to host this conference in 2021. Each annual IEEE ICC conference typically attracts approximately 1,500-2,000 attendees, and will present over 1,000 research works over its duration. As well as being an opportunity to share pioneering research ideas and developments, the conference is also an excellent networking and publicity event, giving the opportunity for businesses and clients to link together, and presenting the scope for companies to publicize themselves and their products among the leaders of communications industries from all over the world.


2020 59th IEEE Conference on Decision and Control (CDC)

The CDC is the premier conference dedicated to the advancement of the theory and practice of systems and control. The CDC annually brings together an international community of researchers and practitioners in the field of automatic control to discuss new research results, perspectives on future developments, and innovative applications relevant to decision making, automatic control, and related areas.


2020 IEEE International Conference on Robotics and Automation (ICRA)

The International Conference on Robotics and Automation (ICRA) is the IEEE Robotics and Automation Society’s biggest conference and one of the leading international forums for robotics researchers to present their work.


2020 IEEE International Instrumentation and Measurement Technology Conference (I2MTC)

The Conference focuses on all aspects of instrumentation and measurement science andtechnology research development and applications. The list of program topics includes but isnot limited to: Measurement Science & Education, Measurement Systems, Measurement DataAcquisition, Measurements of Physical Quantities, and Measurement Applications.


GLOBECOM 2020 - 2020 IEEE Global Communications Conference

IEEE Global Communications Conference (GLOBECOM) is one of the IEEE Communications Society’s two flagship conferences dedicated to driving innovation in nearly every aspect of communications. Each year, more than 2,900 scientific researchers and their management submit proposals for program sessions to be held at the annual conference. After extensive peer review, the best of the proposals are selected for the conference program, which includes technical papers, tutorials, workshops and industry sessions designed specifically to advance technologies, systems and infrastructure that are continuing to reshape the world and provide all users with access to an unprecedented spectrum of high-speed, seamless and cost-effective global telecommunications services.


More Conferences

Periodicals related to Shortest path problem

Back to Top

Automatic Control, IEEE Transactions on

The theory, design and application of Control Systems. It shall encompass components, and the integration of these components, as are necessary for the construction of such systems. The word `systems' as used herein shall be interpreted to include physical, biological, organizational and other entities and combinations thereof, which can be represented through a mathematical symbolism. The Field of Interest: shall ...


Circuits and Systems for Video Technology, IEEE Transactions on

Video A/D and D/A, display technology, image analysis and processing, video signal characterization and representation, video compression techniques and signal processing, multidimensional filters and transforms, analog video signal processing, neural networks for video applications, nonlinear video signal processing, video storage and retrieval, computer vision, packet video, high-speed real-time circuits, VLSI architecture and implementation for video technology, multiprocessor systems--hardware and software-- ...


Circuits and Systems II: Express Briefs, IEEE Transactions on

Part I will now contain regular papers focusing on all matters related to fundamental theory, applications, analog and digital signal processing. Part II will report on the latest significant results across all of these topic areas.


Communications Letters, IEEE

Covers topics in the scope of IEEE Transactions on Communications but in the form of very brief publication (maximum of 6column lengths, including all diagrams and tables.)


Communications Magazine, IEEE

IEEE Communications Magazine was the number three most-cited journal in telecommunications and the number eighteen cited journal in electrical and electronics engineering in 2004, according to the annual Journal Citation Report (2004 edition) published by the Institute for Scientific Information. Read more at http://www.ieee.org/products/citations.html. This magazine covers all areas of communications such as lightwave telecommunications, high-speed data communications, personal communications ...


More Periodicals

Most published Xplore authors for Shortest path problem

Back to Top

Xplore Articles related to Shortest path problem

Back to Top

A Multiobjective Path-Planning Algorithm With Time Windows for Asset Routing in a Dynamic Weather-Impacted Environment

IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2017

This paper presents a mixed-initiative tool for multiobjective planning and asset routing (TMPLAR) in dynamic and uncertain environments. TMPLAR is built upon multiobjective dynamic programming algorithms to route assets in a timely fashion, while considering fuel efficiency, voyage time, distance, and adherence to real world constraints (asset vehicle limits, navigator-specified deadlines, etc.). TMPLAR has the potential to be applied in ...


Erratum to "Vickrey pricing and shortest paths: What is an edge worth?"

The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., 2002

None


The Shortest Path Parallel Algorithm on Single Source Weighted Multi-level Graph

2009 Second International Workshop on Computer Science and Engineering, 2009

Aiming at the single source shortest path problem on the single source weighted multi-level graph, this paper brings forward a new and practical parallel algorithm on 2-D mesh network by constructing a model of vector- matrix multiple and choosing the planar evenly partition method. The parallel algorithm is propitious to handle different sizes of multi-level graph structure by the use ...


Optimal obstacle avoidance based on the Hamilton-Jacobi-Bellman equation

IEEE Transactions on Robotics and Automation, 1997

This paper solves the online obstacle avoidance problem using the Hamilton- Jacobi-Bellman (HJB) theory. Formulating the shortest path problem as a time optimal control problem, the shortest paths are generated by following the negative gradient of the return function, which is the solution of the HJB equation. To account for multiple obstacles, we avoid obstacles optimally one at a time. ...


s-t paths using the min-sum algorithm

2008 46th Annual Allerton Conference on Communication, Control, and Computing, 2008

Solving the distributed shortest path problem has important applications in the theory of distributed systems, most notably routing. In this paper, we provide and prove the convergence of a min-sum algorithm to compute the shortest path between two nodes in a graph with positive edge weights. Unlike the standard distributed shortest path algorithms, the rate of convergence depends on the ...


More Xplore Articles

Educational Resources on Shortest path problem

Back to Top

IEEE-USA E-Books

  • A Multiobjective Path-Planning Algorithm With Time Windows for Asset Routing in a Dynamic Weather-Impacted Environment

    This paper presents a mixed-initiative tool for multiobjective planning and asset routing (TMPLAR) in dynamic and uncertain environments. TMPLAR is built upon multiobjective dynamic programming algorithms to route assets in a timely fashion, while considering fuel efficiency, voyage time, distance, and adherence to real world constraints (asset vehicle limits, navigator-specified deadlines, etc.). TMPLAR has the potential to be applied in a variety of contexts, including ship, helicopter, or unmanned aerial vehicle routing. The tool provides recommended schedules, consisting of waypoints, associated arrival and departure times, asset speed and bearing, that are optimized with respect to several objectives. The ship navigation is exacerbated by the need to address multiple conflicting objectives, spatial and temporal uncertainty associated with the weather, multiple constraints on asset operation, and the added capability of waiting at a waypoint with the intent to avoid bad weather, conduct opportunistic training drills, or both. The key algorithmic contribution is a multiobjective shortest path algorithm for networks with stochastic nonconvex edge costs and the following problem features: 1) time windows on nodes; 2) ability to choose vessel speed to next node subject to (minimum and/or maximum) speed constraints; 3) ability to select the power plant configuration at each node; and 4) ability to wait at a node. The algorithm is demonstrated on six real world routing scenarios by comparing its performance against an existing operational routing algorithm.

  • Erratum to "Vickrey pricing and shortest paths: What is an edge worth?"

    None

  • The Shortest Path Parallel Algorithm on Single Source Weighted Multi-level Graph

    Aiming at the single source shortest path problem on the single source weighted multi-level graph, this paper brings forward a new and practical parallel algorithm on 2-D mesh network by constructing a model of vector- matrix multiple and choosing the planar evenly partition method. The parallel algorithm is propitious to handle different sizes of multi-level graph structure by the use of its simple and regular characteristic, and our algorithm only needs less computation resources. The parallel algorithm was implemented on MPI. The theoretical analysis and the experimental results prove that the parallel algorithm has the good performances in terms of speed- up ratio and parallel efficiency, and its performance is a little better than the parallel dijkstra algorithm.

  • Optimal obstacle avoidance based on the Hamilton-Jacobi-Bellman equation

    This paper solves the online obstacle avoidance problem using the Hamilton- Jacobi-Bellman (HJB) theory. Formulating the shortest path problem as a time optimal control problem, the shortest paths are generated by following the negative gradient of the return function, which is the solution of the HJB equation. To account for multiple obstacles, we avoid obstacles optimally one at a time. This is equivalent to following the pseudo-return function, which is an approximation of the true return function for the multi-obstacle problem. Paths generated by this method are near-optimal and guaranteed to reach the goal, at which the pseudo-return function is shown to have a unique minimum. The proposed method is computationally very efficient, and applicable for online applications. Examples for circular obstacles demonstrate the advantages of the proposed approach over traditional path planning methods.

  • s-t paths using the min-sum algorithm

    Solving the distributed shortest path problem has important applications in the theory of distributed systems, most notably routing. In this paper, we provide and prove the convergence of a min-sum algorithm to compute the shortest path between two nodes in a graph with positive edge weights. Unlike the standard distributed shortest path algorithms, the rate of convergence depends on the weight of the minimal path and not necessarily the number of nodes in the network.

  • Study on Simplified Algorithm for the Shortest Path

    The algorithm of Dijkstra is academic foundation that many engineerings were solved in the shortest path issue,but people must improve and optimize to this algorithm what involves many limitative condition in the real engineering.The minimum labeling algorithm for the shortest path problem is put forward in the paper to avoid burdensome calculation process and failure in display of concrete routes of shortest paths in Dijkstra algorithm. Comparison between the two calculation processes of the minimum labeling algorithm and Dijkstra algorithm on calculation examples in the paper shows the simplification of calculation process in minimum labeling algorithm.

  • DNA Computing for Traveling Salesman Problem

    In this paper, Genetic algorithms is applied to traveling salesman problem whose solution requires encoding of real values in DNA strands. Encode weights in DNA computing is an important but challenging problem because many practical applications in the real world involve weights. In order to efficiently encode weights in DNA strands, we firstly proposed two definitions, the order number of weight and the relative length graph. And then, by means of the two definitions, we have devised a new method of encoding weights in DNA strands for a weighted graph. DNA algorithm solving the traveling salesman problem is given. The effectiveness of the proposed method is verified by simulation. The method was applied to solve the traveling salesman problem, and it can be expanded to solve other numerical optimization problems.

  • Performance Investigation of UCB Policy in Q-learning

    In this paper, we investigated performance and usability of UCBQ algorithm proposed in previous research. This is the algorithm that UCB, which is one of bandit algorithms, is applied to Q-Learning, and can balance between exploitation and exploration. We confirmed in the previous research that it was able to realize effective learning in a partially observable Markov decision process by using a continuous state spaces shortest path problem. We numerically examined it by using a variety of simpler learning situation which is the 2 dimensional goal search problem in a Markov decision process, comparing to previous methods. As a result, we confirmed that it had a better performance than other methods.

  • Soft-decision Decoding of Block Codes using the k Shortest Paths Algorithm

    In this paper, we develop a soft-decision decoding algorithm for block codes using the k shortest paths algorithm. The performance of this algorithm is investigated and compared with other decoding schemes. The results show the proposed algorithm gives large gains over the generalised minimum distance (GMD) decoding algorithm and algebraic hard-decision decoding. Further, the proposed algorithm achieves near-MLD performance for the codes simulated. An investigation of the complexity of this algorithm shows the proposed algorithm to be computationally more efficient than the standard order-l reprocessing algorithm

  • Non-deterministic Algorithm for Routing Optimization: A Case Study

    A routing optimization problem is solved by a non- deterministic algorithm in this paper. The DNA computing is applied for a case of cable trench problem. The cable trench problem is a combination of the shortest path problem and the minimum spanning tree problem, which makes it difficult to be solved by a conventional computing method. DNA computing is applied to overcome the limitation of a silicon-based computer. The numerical values are represented by the fixed-length DNA strands, and the weights are varied by the melting temperatures. Biochemical techniques with DNA thermodynamic properties are used for effective local search of the optimal solution.



Standards related to Shortest path problem

Back to Top

No standards are currently tagged "Shortest path problem"


Jobs related to Shortest path problem

Back to Top