Dijkstra算法及其应用

Dijkstra算法及其应用

摘要:  随着科学的进步发展，电脑信息系统得到广泛和深入的应用.网络分析作为该系统的最主要功能之1，在电子导航、城市规划以及各种通讯网管布局中发挥重要作用，而网络分析中最关键的问题是最短路径问题．最短路径问
题又可以引申为最快路径问题、最低费用问题等，但他们的核心算法都是最短路径算法．经典的最短路径算法——Dijkstra算法是目前多数系统解决最短路径问题采用的理论基础，只是不同系统对Dijkstra算法采用了不同的实现方法．本文主要通过对Dijkstra算法的阐述，分析以及在实际问题中的应用．

关键词:  最短路径;  Dijkstra算法;  应用

The Dijkstra Algorthm and Application

Abstract:  With the development of science, computer information systems has gained extensive and in-depth application. As one of the most important functions of the system, Network Analysis is playing an important role in electronic navigation, town planning and the layout of various communication networks. The most critical problem of Network Analysis is the issue of shortest path issue, which can be likened to the issue of the fastest path issue and the minimum cost whose core algorithms are just that of the shortest path’s. A Classical algorithm for the shortest path--- Dijkstra , is the theoretical basis for most of the current systems in solving the issue of the shortest path. Different systems employ different solutions to Dijkstra algorithm. The author conducts his paper mainly through the demonstration, analysis and the practical application of Dijkstra algorithm.

Key words:  shortest path;  Dijkstra algorthm;  application