艾兹格·W·迪科斯彻 （Edsger Wybe Dijkstra，1930年5月11日~2002年8月6日）荷兰人。 计算机科学家，毕业就职于荷兰Leiden大学，早年钻研物理及数学，而后转为计算学。曾在1972年获得过素有计算机科学界的诺贝尔奖之称的图灵奖，之 后，他还获得过1974年 AFIPS Harry Goode Memorial Award、1989年ACM SIGCSE计算机科学教育教学杰出贡献奖、以及2002年ACM PODC最具影响力论文奖。
艾兹格·W·迪科斯彻(Edsger Wybe Dijkstra)
1 提出“goto有害论”;
2 提出信号量和PV原语;
3 解决了“哲学家聚餐”问题;
4 最短路径算法(SPF)和银行家算法的创造者;
5 第一个Algol 60编译器的设计者和实现者;
6 THE操作系统的设计者和开发者;
与D. E. Knuth并称为我们这个时代最伟大的计算机科学家的人。
与癌症抗争多年，于2002年8月6日在荷兰Nuenen自己的家中去世，享年72岁。
Dijkstra算法C代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h> #define MAXINT 32767
#define MAXNUM 6 char *str = "ABCDEF";
void dijkstra(int *dist, int *prev, int (*A)[MAXNUM], int v0);
void findPath(int *dist, int *prev, int start, int end); int main()
{ int A[MAXNUM][MAXNUM] = {{, , , MAXINT, MAXINT, MAXINT},
{, , , , MAXINT, MAXINT},
{, , , , , MAXINT},
{MAXINT, , , , , },
{MAXINT, MAXINT, , , , },
{MAXINT, MAXINT, MAXINT, , , },
};
int dist[MAXNUM] = {};
int prev[MAXNUM] = {};
int v0 = , i = ; dijkstra(dist, prev, A, v0); findPath(dist, prev, v0, ); //for(i = 0; i < MAXNUM; i++)
{
// printf("%d ", prev[i]);
} system("pause");
return ;
} void findPath(int *dist, int *prev, int start, int end)
{
int tmp = prev[end];
int *rst = (int*)calloc(MAXNUM, sizeof(int));
int cnt = , i = ;
rst[cnt] = end;
cnt++;
if(tmp == start)
{
rst[cnt] = tmp;
}
else
{
while(tmp != start)
{
rst[cnt] = tmp;
tmp = prev[tmp];
cnt++;
}
rst[cnt] = tmp;
} //printf("%d\n", cnt);
for(i = cnt; i >= ; i--)
{
printf("%c", str[rst[i]]);
if(i != )
{
printf("->");
}
}
printf(" %d\n", dist[end]); free(rst);
rst = NULL; } void dijkstra(int *dist, int *prev, int (*A)[MAXNUM], int v0)
{
int S[MAXNUM];
int n = MAXNUM, i = , j = ;
for (i = ; i < n; i++)
{
dist[i] = A[v0][i];
S[i] = ;
if(dist[i] == MAXINT)
{
prev[i] = -;
}
else
{
prev[i] = v0;
// printf("%c前驱%c\n", str[i], str[v0]);
}
}
dist[v0] = ;
S[v0] = ; for(i = ; i < n; i++)
{
int mindist = MAXINT;
int u = v0;
for(j = ; j < n; j++)
{
if((!S[j]) && dist[j] < mindist)
{
u = j;
mindist = dist[j];
}
}
S[u] = ; for(j = ; j < n; j++)
{
if((!S[j]) && A[u][j] < MAXINT)
{
if(dist[u] + A[u][j] < dist[j])
{
dist[j] = dist[u] + A[u][j];
prev[j] = u;
// printf("%c前驱%c\n", str[j], str[u]);
}
}
}
}
}
代码仅供参考
参考资料