Dijkstra：宗师、巨星，计算机学科的奠基人之一

??
??牛顿有句名言：“如果我看得比别人更远些，那是因为我站在巨人们的肩膀上¹。

??在计算机科学界，荷兰人Edsger W. Dijkstra（EWD，狄克斯特拉）是公认的的巨人，抗起计算机学科发展的奠基人之一。从22岁到70岁近40年，他在计算机软件和理论方面做了很多开创性工作，伴随着计算机学科从懵懂到成熟的年代。他创造了大量常用的、写入权威教科书的基本计算机概念和术语，制订了很多编程技术的指导性原则，例如堆栈（stack）、显示（display）、信 量（semaphore）、死锁（deadlock）、互斥（mutual exclusion）、结构化编程（structured programming）等等。
??Dijkstra获得无数荣誉，其中最有名的是ACM图灵奖。1972年第七届图灵奖，当Dijkstra得知自己获奖时，十分惊讶，因为这个美国ACM协会设置的奖很少颁给非美国人。而且，直到24年后的1996年，才有第2个非英美人获奖。
??在1966-2000年间，共有41人获ACM图灵奖，其中：“美国出生+美国求学+美国工作”27人；“非美国出生+美国求学+美国工作”8人；其他6人，这6人中有4个英国人，1个荷兰人（1972年Dijkstra），1个以色列人（1996年的Amir Pnueli）。
??2001-2019年间，非美国获奖者多了起来。共30名获奖者，其中“美国出生+美国求学+美国工作”18人，“非美国出生+美国求学+美国工作”3人，其他9人。

??Dijkstra简历：
??1952–1962：荷兰阿姆斯特丹计算机部，程序员
??1962–1973：荷兰埃因霍芬理工大学数学系，教授
??1973–1984：美国Burroughs Corporation公司，研究员
??1984–2000：美国德克萨斯大学奥斯汀分校，教授

1、引子
??大部分计算机学生是在学习“Dijkstra最短路径算法”时得知Dijkstra的。图论中有两个著名的算法：Dijkstra最短路径算法和Prim最小生成树算法²。两个算法的思想基本一样，都是基于贪心法来扩展结点，执行步骤十分相似，代码只有微小差别。两个算法简单而高效，现在仍广泛应用在图问题中，例如手机的地图导航、游戏软件的寻路等。

??这两个算法虽然以发明者的名字“Dijkstra”、“Prim”命名，但其实有好几位科学家独立发明过，其中一人是Dijkstra。1956年，他26岁做兼职程序员时曾在一篇论文中同时提出了这两个算法。这篇只有3页的小论文“A note on two problems in connection with graphs³”，第一部分现在一般被称为“Prim最小生成树算法”，第二部分现在一般被称为“Dijkstra最短路径算法”。

??Dijkstra最短路径算法的思路很简单，它维护两个集合：一个是已经计算出最短路径的结点集合A，另一个是这些点向外扩散的邻居结点集合B。算法的执行步骤是：扩展A的直连邻居，放到B中；每次从B中取出距离起点最短的结点，放到A中；当B为空时计算结束。

??1960年，Dijkstra和同事一起编写ALGOL 60编译器，这是世界上第一个ALGOL 60编译器。开发过程中解决了很多关键问题，例如1960年Dijkstra在一篇论文“Recursive Programming”中，提出了术语“堆栈（stack）”。多年以后，他得知这篇小论文让他在美国计算机学界出了名。

1. https://www.phrases.org.uk/meanings/268025.html ??

2. R. C. Prim, “Shortest Connection Networks and some Generalizations,” Bell System Technical Journal, Vol. 36, 1957, pp. 1389-1401. ??

3. Edsger W. Dijkstra, “A note on two problems in connection with graphs,” Numerische Mathematik 1, 1959, pp. 269–271. 下载：http://www-m3.ma.tum.de/foswiki/pub/MN0506/WebHome/dijkstra.pdf ??

4. The Man Who Carried Computer Science on His Shoulders
   https://inference-review.com/article/the-man-who-carried-computer-science-on-his-shoulders ??

5. Dijkstra自传：“We were very poor, …, but life was incredibly exciting.” ??

6. Dijkstra自传：“the first Dutchman with the qualification ‘programmer’ on the payroll.” ??

7. A case against the GO TO statement https://www.cs.utexas.edu/users/EWD/ewd02xx/EWD215.PDF ??

8. “Notes on Structured Programming”: https://www.cs.utexas.edu/users/EWD/ewd02xx/EWD249.PDF ??

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览35078 人正在系统学习中