Dijkstra's algorithm and L-concave function maximization
成果类型：
Article
署名作者：
Murota, Kazuo; Shioura, Akiyoshi
署名单位：
University of Tokyo; Tohoku University
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-013-0643-2
发表日期：
2014
页码：
163-177
关键词：
摘要：
Dijkstra's algorithm is a well-known algorithm for the single-source shortest path problem in a directed graph with nonnegative edge length. We discuss Dijkstra's algorithm from the viewpoint of discrete convex analysis, where the concept of discrete convexity called L-convexity plays a central role. We observe first that the dual of the linear programming (LP) formulation of the shortest path problem can be seen as a special case of L-concave function maximization. We then point out that the steepest ascent algorithm for L-concave function maximization, when applied to the LP dual of the shortest path problem and implemented with some auxiliary variables, coincides exactly with Dijkstra's algorithm.