第五章_Dijkstra_最短路径算法.pdfVIP

第五章_Dijkstra_最短路径算法--第1页

Dijkstra：最短路径算法

（1）个人简介

艾兹格·W·迪科斯彻（EdsgerWybeDijkstra，1930年5月11日~2002年8月6日）荷

兰人。计算机科学家，毕业就职于荷兰Leiden大学，早年钻研物理及数学，而后转为计算

学。曾在1972年获得过素有计算机科学界的诺贝尔奖之称的图灵奖，之后，他还获得过1974

年AFIPSHarryGoodeMemorialAward、1989年ACMSIGCSE计算机科学教育教学杰出贡

献奖、以及2002年ACMPODC最具影响力论文奖。

——《百度百科》

Dijkstra是计算机科学最具影响力的创始人之一，从工程和理论角度帮助塑造了新的学

科。他的基础贡献涵盖了计算科学的各个领域，包括编译器构建，操作系统，分布式系统，

顺序和并发编程，编程范式和方法，编程语言研究，程序设计，程序开发，程序验证，软件

工程原理，图形算法以及计算机编程和计算机科学的哲学基础。他的许多论文都是新研究领

域的来源。现在计算机科学中的几个概念和问题是由迪克斯特拉首先确定的，或者是由他创

造的熊的名字。

20世纪50年代到60年代的计算机编程没有被认为是一门学科。在20世纪60年代后

期，计算机编程处于危机之中。他是一小群学者和工业程序员之一，他们提倡采用新的编程

风格来提高程序的质量。Dijkstra拥有数学和物理学背景，是接受计算机编程作为一门科学

学科的推动力之一。他创造了“结构化程序设计”这个词，并在20世纪70年代成为了新的

编程正统。他关于结构化编程的想法帮助奠定了软件工程专业学科诞生和发展的基础，使程

序员能够组织和管理日益复杂的软件项目。正如伯特兰·迈耶（2009）指出，“在视图中编程

由Dijkstra的圣像破坏运动开始的革命导致了被称为结构化编程一个运动，它倡导一种系统

的，合理的方法来进行编程结构。结构化编程基础这是自编程方法学以来所做的一切，包括

面向对象编程。“

并发计算的学术研究始于20世纪60年代，Dijkstra（1965）认为这是该领域的第一篇

论文，确定并解决了互斥问题。他也是分布式计算原理研究的早期先驱之一。他对基础工作

的并发，信号量，互斥，死锁（死锁），发现在图表最短路径，容错，自稳，其中许多其他

贡献包括构建分布式计算领域的许多支柱。他在2002年去世之前不久，因其计划计算的自

我稳定工作而获得ACMPODC分布式计算的影响力纸奖。这一年度奖项是为了纪念他，于

次年更名为Dijkstra奖（EdsgerW.Dijkstra分布式计算奖）。

——《维基百科》

第五章_Dijkstra_最短路径算法--第1页

第五章_Dijkstra_最短路径算法--第2页

（2）非凡风采

Dijkstra2002年图艾兹格·W·迪科斯彻

（3）主要贡献

作为计算科学许多研究领域的早期理论先驱，Dijkstra从工程和学术角度帮助塑造了新

的学科。他的许多论文都是新研究领域的来源。现在许多计算机科学标准的概念首先由

Dijkstra创造的。他还首先制定和解决了几个重要的问题。1994年对1000多名计算机科学

教授进行了一项调查，以获得该领域38份最有影响力的学术论文清单，而迪杰斯特拉是五

篇论文的作者。