本文为原创，可能有一些不太严肃的胡说，请勿转载。
Dijkstra：宗师、巨星，计算机学科的奠基人之一
牛顿有句名言：“如果我看得比别人更远些，那是因为我站在巨人们的肩膀上1。
Edsger W. Dijkstra（狄克斯特拉）是计算机学科的巨人，是计算机软件和理论的奠基人之一。他创造了很多现在常用的计算机概念和术语，制订了很多编程技术的指导性原则，例如堆栈（stack）、显示（display）、信号量（semaphore）、死锁（deadlock）、互斥（mutual exclusion）、结构化编程（structured programming）等等。
Dijkstra获得无数荣誉，其中最有名的是ACM图灵奖。Dijkstra得知自己获图灵奖时，十分惊讶，因为这个美国ACM协会设置的奖很少颁给非美国人。
在1966-2000年间，共有43人获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最短路径算法和Prim最小生成树算法2。两个算法的思想基本一样，都是基于贪心法来扩展结点，执行步骤十分相似，代码只有微小差别。两个算法简单而高效，现在仍广泛应用在图问题中。
这两个算法虽然以发明者的名字“Dijkstra”、“Prim”命名，但其实有好几位科学家独立发明过，其中一人是Dijkstra，他26岁做兼职程序员时曾在一篇论文中同时提出了这两个算法。这篇只有3页的小论文“A note on two problems in connection with graphs3”，第一部分现在一般被称为“Prim最小生成树算法”，第二部分现在一般被称为“Dijkstra最短路径算法”。
Dijkstra算法维护两个集合：一个是已经计算出最短路径的结点集合A，另一个是这些点向外扩散的邻居结点集合B。算法的执行步骤是：扩展A的直连邻居，放到B中；每次从B中取出距离起点最短的结点，放到A中；当B为空时计算结束。
不过，论文中没有提到一个关键问题：如何高效地从B中选出距离起点最短的那个点？这个问题的解决决定了算法的复杂度，决定了代码的效率有多好。现在参加算法竞赛的学生都知道，编程时一般用优先队列（效率极高，n个数只需要计算logn次就能找到最小的数）来实现。但是在Dijkstra的论文中，并没有提到如何实现，也许他认为这是一个需要扩展的问题，也可能那时候还没有这些数据结构的概念吧。
Dijkstra在1956年发明了这个算法，但那时还没有自动计算方面的专业期刊，直到1959年才找到合适的刊物发表。这篇论文是1945-2000年间Web of Science数据库中的一篇经典引文。在一次关于Dijkstra算法的通信中，Douglas McIlroy教授谈到了Dijkstra算法表达的现代性，指出“它在当时显然是不寻常的。后来的上千次引用也不能对它有所改进。”
Dijkstra对计算机学科的发展有很多奠基性的贡献，最短路径算法只是他年轻时走过的一个小脚印。Dijkstra于1956年提出最短路径算法，时年26岁，是他作为一个计算机科学家的开端。之后的30年，他发展了现在众所周知的、成为常识的多种计算机概念和技术，他那“巨人的肩膀，扛起了计算机科学4”。
2、生平
简单地概况Dijkstra的成功人生：书香门第、天资聪颖、勤学好思、抓住机遇、工作努力、交游广泛。
1930年，Dijkstra出生于荷兰城市鹿特丹（Rotterdam），是四个孩子中的老三。他有个好家庭。他父亲是中学化学老师和中学校长，但不是一个普通的化学老师，而是一个化学家、荷兰化学学界的名人，当过荷兰化学协会的主席，博学多才。他母亲是数学家，不过没工作而是家庭妇女（那个年代的女性都这样），她非常聪明，是个天才，Dijkstra说他从母亲那里学到了如何简洁优雅地解决问题。
Dijkstra又聪明又勤学，学习成绩非常好。中学毕业后，他原本想去学法律，但是长辈们都建议他不要浪费自己的聪明才智，应该去从事科学事业。1948年，他到离家不远的莱顿大学（University of Leiden）读物理学，他说他的大学生涯“很穷很累很快乐5”。这不奇怪，那时正是二战后的欧洲重建时期。
大学的头三年，Dijkstra老老实实学物理和数学，1951年通过中期考试，比其他同学都早。然而Dijkstra一直到1956年才拿到大学学位，一共读了8年大学。读了这么久，不是因为去游戏人生了，而是因为他对物理的兴趣衰退了，中间去兼职工作当了一名程序员。
1951年，一件事改变了Dijkstra的命运。计算机科学的一颗星星开始升起，这将是一颗星等为一等的亮星。
这一年，他那热爱科学并积极关注科学发展的父亲，看到剑桥大学的一个编程课广告，一门三星期的短课，学习EDSAC计算机编程。EDSAC是世界第一台存储程序式电子计算机，采用了冯诺依曼结构。作为对Dijkstra提前通过中期考试的奖励，父亲资助他去英国学编程，可能真实目的是让他去剑桥大学见见世面，顺便路过伦敦逛逛吧。好学的Dijkstra觉得用计算机来帮助做数值计算，有利于物理研究，于是高兴地去了。
Dijkstra在编程课上偶遇阿姆斯特丹数学中心的负责人。负责人对他说计算机刚起步，有光明的发展前景，注定成为一门显学，“小伙子你会成为计算机宗师的”。然后热情邀请他到数学中心做编程工作，而且宜早不宜迟，机会不等人。Dijkstra面临一个重大选择，是继续读物理，还是去搞编程？他决定一起做。
从1952年开始，Dijkstra大部分时间都在数学中心兼职搞编程，物理学业差不多荒废了，导致他到1956年才从大学毕业。毕业后，他在数学中心全职工作，一直到1962年。
他在自传中戏称自己是“第一个靠编程赚钱的荷兰人6”，在图灵奖获奖感言中也说自己是荷兰的第一个程序员。
看到这里，我们发现Dijkstra当初其实是被数学中心负责人忽悠了。荷兰那时几乎没有人会编程，连一个只学了3周编程的Dijkstra也成了稀缺人才。数学中心的负责人之所以向Dijkstra伸出橄榄枝，根本原因是没有选择，只能找他。
在数学中心当程序员，听起来不错：敲着键盘，喝着咖啡，工作之余还能打打游戏…这都是做梦，那时还没有电脑键盘，输入靠穿孔纸带，输出靠电传打字机，电脑屏幕自然也没有。至于编程嘛，高级语言还没有出现，汇编语言也没有，因为电脑还没有编译编程语言的能力，只能直接用机器码编程，就是0和1。现在编程语言教科书上的知识，当时几乎都没有。Dijkstra在剑桥学的就是这种编程，怪不得只要3周，因为也没什么好学的。Dijkstra没有被这种枯燥的工作吓倒，反而产生了浓厚的兴趣，数学中心负责人肯定高兴坏了。
Dijkstra在数学中心的十年编程工作颇有成效，最短路径算法就是这个期间发明的，这是Dijkstra设计的第一个著名算法，并以他的名字命名。Dijkstra为此感到很得意，他在1993年的自传中回忆这一美妙时光：“最短路径算法以我的名字命名，让我出了名。当初我设计这个算法的时候，并没有拿着纸和笔冥思苦想。那是在阿姆斯特丹的一个露天咖啡馆，我和妻子（当时在谈恋爱，一年后的1957年结婚）晒着阳光喝着咖啡，然后我灵机一动想到了这个算法。”
1960年，Dijkstra和同事一起编写ALGOL 60编译器，这是世界上第一个ALGOL 60编译器。开发过程中解决了很多关键问题，例如1960年Dijkstra在一篇论文“Recursive Programming”中，提出了术语“堆栈（stack）”。多年以后，他得知这篇小论文让他在美国计算机学界出了名。
因为在数学中心的工作，Dijkstra于1959年获得了阿姆斯特丹大学的博士学位，博士论文题目是“Communication with an Automatic Computer”，研究实时中断问题。
Dijkstra在数学中心工作到1962年，这期间的工作让他成为一位有名的计算机科学家，他这颗星星开始在天空眨眼。
1962年，他被聘为荷兰埃因霍芬理工大学（Eindhoven University of Technology）数学系的教授。不过，他说自己其实是第3个候选人，只是因为前2人拒绝了聘请，才轮到他。学校给他安排的工作是上《数值分析》课，课余他组织了一个计算机研究小组，开发“THE Multiprogramming System”。“THE”系统创造了历史，是世界第一个松耦合、显式同步、协操作串行处理的操作系统，在大学的计算中心运行了10年。信号量（semaphore）、死锁（deadlock）等新概念就是在这个系统上提出的。他很为这个系统自豪，他到英国、美国交流这个系统的设计，获得了同行的高度认可，使他在计算机学界声名鹊起。
Dijkstra最广为人知的事情，是他对GO TO语句的批评。当时人们在编程时，经常使用GO TO语句，随意跳转到程序的任意位置。这个语句极为暴力，让程序的流程变得支离破碎。敏锐的Dijkstra第一个认识到这个语句对程序逻辑、计算资源的的破坏性。1968年他给 Communications of the ACM写了一篇2页纸的通讯，信件原标题是“反对GO TO语句（A case against the GO TO statement7）”，因为过于露骨，被编辑改名为较为温和的“Go To Statement Considered Harmful”后发表，引起了广泛的争论。当然，现在大家都知道他赢了，几乎没有人在编程的时候使用GO TO语句。这封信影响如此之大，以至于“X considered harmful”成了一个标题模板，经常被用于咆哮和指责的文章中。
1969年，他为了平复自己郁闷的心情（后文说明了原因：他不受自己工作的大学的待见，他的研究小组被解散），花大气力写了一篇80多页的报告“Notes on Structured Programming8”，即“结构化编程”。结构化编程现在是计算机程序默认的基本原则，不过那时还是一个全新的概念。他复制了20份，寄给外国的朋友，因为他觉得这只是一篇普通的报告，让大家看看就好了。然而出乎他的意料，这篇报告获得了巨大的成功，“像野火一样传播（spread like wildfire）”，辗转复印了很多轮，Dijkstra自己就认识一个住在偏远角落的人珍藏着这篇报告的第5、6代复印稿。“洛阳纸贵”，一时间人人都在看这篇伟大的报告，深深为Dijkstra充满哲人的洞见而折服。Dijkstra后来分析为什么受到欢迎：“这是第一篇严肃讨论编程挑战的文章。” 这份报告终于奠定了他计算机科学巨星的地位。
Dijkstra声誉日隆。1972年他接到一个美国电话，被告知获得了第七届ACM图灵奖。Dijkstra非常震惊，没想到自己能得这个奖，因为前6个图灵奖获得者都是美国人或英国人。Dijkstra的震惊是可以理解的，如果他晚一些年获得图灵奖，他会更加震惊，因为一直到1996年，才有第2个非英美的获奖者。姚期智2000年获得图灵奖，是图灵奖唯一的华裔学者，当时他是美国国籍。姚期智于2016年放弃美籍，成为中国公民。
然而，Dijkstra在学校的地位却越来越尴尬。就在获得ACM图灵奖之后不久，他就从大学离职了。大环境是计算机学科在1960年代中期才在英美的一些大学出现，而Dijkstra所在的大学那时还没有。他所在的数学学院的领导并不太理解和支持他的计算机工作，觉得他不务正业。他搞的计算机研究，和学院其他老师做的数学研究似乎毫不搭边。另外，Dijkstra在自传中用忧郁的语气回忆自己当时“穿拖鞋、留胡子、态度傲慢”，这不修边幅的样子和现代程序员的邋遢风格一样，一点儿都不像个教授，Dijkstra的人缘似乎不太好。他成了他所在大学的一个异类，学校甚至解散了他的研究小组，他成了一个孤家寡人。甚至1972年获得图灵奖，这个荣誉也没有让他在学校的地位有所好转。院长大人似乎不知道什么是图灵奖，当Dijkstra兴奋地第一时间跑去告诉他自己得了图灵奖，院长脱口而出说了一句伤人的话：“计算机的奖是不是太多了（In the world of computing, they are rather lavish with prizes, aren’t they?）？” 年轻的科学巨星、计算机宗师被说得如此不堪，Dijkstra记了一辈子。
1973年，他从大学离职，找了个新工作，新东家是当时著名的美国计算机制造商Burroughs Corporation公司，办公地点就在他荷兰的家里。这是一份美妙的工作，他没有具体任务，而是“自由研究”，只需要每年去美国总部汇报几次就好了。在做“自由研究员”的那些年，他跑遍了世界各国，参加各种学术会议，在计算机的世界中自由飞翔。
然而，美妙时光不会永远持续。1984年，他从Burroughs Corporation公司离职，因为“Burroughs的学术视野正在缩小，而我的视野正在扩大。” Burroughs Corporation公司在走下坡路，开始节流了。
美国的好客和学术环境吸引着Dijkstra。他终于在54岁的年龄离开了荷兰，到美国德克萨斯大学奥斯汀分校做计算机教授。1999年退休，2002年查出癌症，回到荷兰后不久去世。
Dijkstra一生著述极多。他做事非常有条理，用自己名字的缩写“EWD”对这些文件进行命名和编号，一共有1318篇，德克萨斯大学把这1318篇作品整理成档案在网上公开。有趣的是，他是一位计算机科学家，却几乎不用电脑打字，而习惯于用钢笔书写。这1318篇作品，除了早期的一部分已经找不到手稿，后期的手稿都在，字迹工工整整，几乎没有涂改的痕迹。这些手稿的笔迹，数十年完全一致，显然出自同一人的手笔，不是别人誊抄的。有的手稿长达几十页，是很不容易的。
他的最后一篇“EWD1318”，写于2002年4月，当时已经回到荷兰，4个月后去世。绚烂的生命之花，在日暮时分凋落。
本文参考了以下原始资料：
[1]Dijkstra自传：https://www.cs.utexas.edu/users/EWD/ewd11xx/EWD1166.PDF
[2]Dijkstra档案：https://www.cs.utexas.edu/users/EWD/
[3]ACM图灵奖介绍：https://amturing.acm.org/award_winners/dijkstra_1053701.cfm
R. C. Prim, “Shortest Connection Networks and some Generalizations,” Bell System Technical Journal, Vol. 36, 1957, pp. 1389-1401. ↩︎
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 ↩︎
The Man Who Carried Computer Science on His Shoulders
https://inference-review.com/article/the-man-who-carried-computer-science-on-his-shoulders ↩︎Dijkstra自传：“We were very poor, …, but life was incredibly exciting.” ↩︎
Dijkstra自传：“the first Dutchman with the qualification ‘programmer’ on the payroll.” ↩︎
A case against the GO TO statement https://www.cs.utexas.edu/users/EWD/ewd02xx/EWD215.PDF ↩︎
“Notes on Structured Programming”: https://www.cs.utexas.edu/users/EWD/ewd02xx/EWD249.PDF ↩︎
转载：https://blog.csdn.net/weixin_43914593/article/details/114755499