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

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分布式计算奖）。
——《维基百科》
（2）非凡风采

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

（3）主要贡献

作为计算科学许多研究领域的早期理论先驱，Dijkstra从工程和学术角度帮助塑造了新
的学科。他的许多论文都是新研究领域的来源。现在许多计算机科学标准的概念首先由
Dijkstra创造的。他还首先制定和解决了几个重要的问题。1994年对1000多名计算机科学

教授进行了一项调查，以获得该领域38份最有影响力的学术论文清单，而迪杰斯特拉是五
篇论文的作者。
作为计算科学家，他在计算科学家中担任过四十多年，包括学术界和工业界的职位，
Dijkstra在许多计算科学领域做出了许多开创性贡献，其中包括编译器构建，操作系统，并

发编程（并行计算），分布式编程编程范式和方法论，编程语言研究，程序设计，程序开发，

程序验证，软件工程原理，算法设计和计算机编程和计算机科学的哲学基础。另外，Dijkstra
对计算机科学教学以及学术计算科学和软件行业之间的关系非常感兴趣。
——《维基百科》

（4）名人故事

EdsgerWybeDijkstra于1930年5月11日生于鹿特丹Rotterdam，他的父亲，DouweWybe
Dijkstra是一位化学家，他的母亲，BrechtjeCorneliaKruyper是一位数学家，这种充满科学气息的
家庭背景对于他的职业生涯乃至他的整个人生都有着深刻的影响。EdsgerWybeDijkstra在当地的
GymnasiumErasmianum读高中，1948年，他考入了Leyden大学。他在联合国从事法律方面的工
作时却在怀念在Erasmianum的日子。之后，他选择了数学和物理。
首次体验程序设计
EdsgerWybeDijkstra在三年之内取得了学士学位，这令他的父亲非常高兴，并在1951年9
月同意他去英国参加一个夏季的课程，那是一个由剑桥大学开设的，学习电子计算装置程序设计的课

程，讲师是著名的威尔克斯（MauriceVincentWilkes），EdsgerWybeDijkstra的导师让他给
Amsterdamr数学中心计算部门的主管AadvanW