狄克斯特拉算法研究论文

狄克斯特拉1930年5月11日生于荷兰鹿特丹的一个知识分子家庭，在兄弟姊妹4人中排行第三。他的父亲是一名化学家和发明家，曾担任荷兰化学会主席。他母亲则是一位数学家。狄克斯特拉的少年时代是在德国法西斯占领军的铁蹄下度过的。由于食物短缺，他被送到乡下他父亲的一个朋友那里去。纳粹德国投降后，1945年7月，十分虚弱的狄克斯特拉才和家人重新团聚。狄克斯特拉原打算学法律，毕业后到联合国工作，为维护世界和平服务。但他中学毕业时，数理化成绩都特别好，因此他父亲说服了他，1948年进莱顿大学学习数学与物理。在学习理论物理的过程中，狄克斯特拉发现这个领域中的许多问题都需要进行大量复杂的计算，于是决定学习计算机编程。1951年，他自费赴英国参加了剑桥大学举办的一个程序设计培训班，学习在EDSAC(Electronic Delay Storage Automatic Calculator，这是由另一位首届计算机先驱奖获得者威尔克斯主持设计与开发的世界上第一台存储程序式电子计算机)上的编程方法，这使他成为世界上第一批程序员之一。第二年，阿姆斯特丹数学中心了解到这一情况，拟聘他为兼职程序员。狄克斯特拉开始时有些犹豫，因为世界上当时还没有“程序员”这一职业。数学中心的计算部主任、Algol语言的设计者之一、荷兰的计算技术先驱维京格尔藤(A．van Wijingaarden，1916—1987，因在设计Algol 68时，为解决上下文有关性这一难题而提出了一种具有很强描述能力的新的文法，称做二级文法又称W文法而闻名。他是1986年计算机先驱奖获得者之一，也曾对另一位首届计算机先驱奖获得者N．Wirth的研究产生过影响)对他说，目前程序设计虽然还没有成为学科，不被重视，但既然计算机已经有了，正处于开创阶段，你未来就有可能使程序设计成为一个受人尊敬的学科。这段话说动了狄克斯特拉，使他接受了这个职位，而且越干越有兴趣，这样，他在第二年就结束了在莱顿大学的学业，成为数学中心全日制的工作人员，从此进入计算机领域，并且正如维京格尔藤所预言的那样，逐渐成为该领域的知名专家，创造出了许许多多的“第一”。1956年，他成功地设计并实现了在有障碍物的两个地点之间找出一条最短路径的高效算法，这个算法被命名为“狄克斯特拉算法”，解决了机器人学中的一个十分关键的问题，即运动路径规划问题，至今仍被广泛应用，被认为是利用“贪心法”(greedy method)设计算法的一个成功范例。1959年，在数学中心将他们原先的ARMAC计算机进行升级的过程中，狄克斯特拉设计了一种处理程序，成功地解决了“实时中断”（real-time interrupt)问题。狄克斯特拉的博士论文就是以此为课题完成的，并在阿姆斯特丹大学通过论文答辩而获得博士学位。1960年8月，Algol 60文本推出刚刚半年多，狄克斯特拉和他在数学中心的同事仲纳凡尔特(J．A．Zonneveld)一起就率先实现了世界上第一个Algol 60编译器，比欧美其他各国学者实现Algol 60早一年还多。这一成就引起各国计算机学者的惊叹，并因此奠定了狄克斯特拉作为世界一流计算机学者在科学界的地位。1962年，狄克斯特拉离开数学中心进入位于荷兰南部的艾恩德大学(Eindhoven Technical University)任数学教授。在这里，X8计算机的开发，设计与实现了具有多道程序运行能力统——THE Multiprogramming System。THE是艾恩德霍芬技荷兰文Technische Hoogeschool Eindhoven的词头缩写。狄克THE这个系统中所提出的一系列方法和技术奠定了计算作系统的基础，尤其是关于多层体系结构、顺序进程之间的斥机制这样一些重要的思想和概念都是狄克斯特拉在THE中首先提出并为以后的操作系统如UNIX等所采用的。为了在单处理机的情况下确定进程(process)能否占有处理机，狄克斯特拉将每个进程分为“就绪”(ready)、“运行”(running)和“阻塞”(blocking)三个工作状态。由于在任一时刻最多只有一个进程可以使用处理机，正占用着处理机的进程称为“运行”进程。当某进程已具备了使用处理机的条件，而当前又没有处理机供其使用，则使该进程处于“就绪”状态，当运行进程由于某种原因无法继续运行下去时，就停止其占用处理机，使之进入“阻塞’’状态，待造成其退出运行的条件解除，再进入“就绪”状态。而对系统中所有同时运行的进程之间所存在的相互制约的同步(synchronization，指为了避免错误，在一个进程访问共享数据时，另一个进程不访问该数据)和互斥(mutually-exclusive，指两个进程不能同时在一个临界区中使用同一个可重复使用的资源，诸如读写缓冲区)两个关系，狄克斯特拉巧妙地利用火车运行控制系统中的“信号灯”(semaphore，或叫“信号量”)概念加以解决。所谓信号灯，实际上就是用来控制进程状态的一个代表某一资源的存储单元。例如，P1和P2是分别将数据送入缓冲B和从缓冲B读出数据的两个进程，为了防止这两个进程并发时产生错误，狄克斯特拉设计了一种同步机制叫PV操作”，P操作和V操作是执行时不被打断的两个操作系统原语。执行P操作P(S)时信号量S的值减1，若结果不为负则P(S)执行完毕，否则执行P操作的进程暂停以等待释放。执行V操作V(S)时，S的值加1，若结果不大于0则释放一个因执行P(S)而等待的进程。对P1和凹可定义两个信号量S1和S2，初值分别为1和0。进程P1在向缓冲B送人数据前执行P操作P(S1)，在送人数据后执行V操作V(S2)。进程P2在从缓冲B读取数据前先执行P操作P(S2)，在读出数据后执行V操作V(S1)。当P1往缓冲B送入一数据后信号量S1之值变为0，在该数据读出后S1之值才又变为1，因此在前驱数未读出前后续数不会送入，从而保证了P1和P2之间的同步。我国读者常常不明白这一同步机制为什么称做PV操作，原来这是狄克斯特拉用荷兰文定义的，因为在荷兰文中，通过叫passeren，释放叫，VRIJGEVEN，PV操作因此得名。这是在计算机术语中不用英语表达的极少数的例子之一。

一直想要学点简单的算法，叨叨了好久，开始吧【这篇文章的前言无非就是我想说点废话，大家可以选择性的过滤哈。】

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家 狄克斯特拉 于1959 年提出的，因此又叫 狄克斯特拉算法 。是从一个顶点到其余各顶点的 最短路径 算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

敲黑板~进入正题 迪杰斯特拉算法是目前 OIER 们最爱用的最短路算法，下面讲一下这个算法的思路【图丑，请大家忍耐一下】：

第一步，我们先把a加入集合，数组变成（s = {a}, dis[] = {0, ∞,∞,∞,∞,∞,∞,∞}） 第二步，找到和a最近的点，为b，把b加入集合，并确定他的最短路径【要注意箭头方向哈】，数组变成（s = {a, b}, dis[] ={0,2,∞,∞,∞,∞,∞,∞}） 第三步，找到和b最近的点，为d，把d加入集合，并确定他的最短路径【要注意箭头方向】，数组变成（s = {a, b, d}, dis[] = {0,2,∞,3,∞,∞,∞,∞}） 第四步，找到和d最近的点，为e，把e加入集合，并确定他的最短路径【要注意箭头方向】，数组变成（s = {a, b, d, e}, dis[] = {0,2,∞,3,5,∞,∞,∞}） 第五步，找到和e最近的点，为f，把f加入集合，并确定他的最短路径【要注意箭头方向】，数组变成（s = {a, b, d, e, f}, dis[] = {0,2,∞,3,5,9,∞,∞}） 第六步，找到和f最近的点，为g，把g加入集合，并确定他的最短路径【要注意箭头方向】，数组变成（s = {a, b, d, e, f, g}, dis[] = {0,2,∞,3,5,9,12,∞}） 第七步，目前只剩下c和h了，那么我们先要找到距离集合路径最短的c，把c加入集合，并确定他的最短路径，数组变成（s = {a, b, c, d, e, f, g}, dis[]= {0,2,13,3,5,9,12,∞}） 第八步，最后一步，我们找到距离集合路径最短的h，把h加入集合，并确定他的最短路径，数组变成（s = {a, b, c, d, e, f, g, h}, dis[] = {0,2,13,3,5,9,12,18}） 得嘞，这个大致的思路是这样的，还有后续哟，欲知后事如何，请看下回讲解~