算法

↑ 上图是帮助理解的。只要认真看懂 ↑↑ 这张图，其他的问题不大。

　　(下面程序中的图会稍微简单一些。)

　　下面 ↓ 是代码的图，可以对照着在脑海中，草纸上把程序过一遍，以加深理解。轮子哥说：如何记忆算法？把算法运用的像1+1=2一样熟练就可以了。!

　　()

　　迪杰斯特拉算法的证明包含在下面：

　　算法思想

　　-令G = （V，E）为一个带权有向图，把图中的顶点集合V分成两组，

　　第一组为已求出最短路径的顶点集合S（初始时S中只有源节点，以后每

　　求得一条最短路径，就将它对应的顶点加入到集合S中，直到全部顶点都加入到S中）；第二组是未确定最短路径的顶点集合U。在加入过程中，

　　总保持从源节点v到S中各顶点的最短路径长度小于(或等于)从源节点v到U中任意顶点的路径长度。

　　(1)初始化时，S只含有源节点；

　　(2)从U中选取一个距离v最小的顶点k加入S中（该选定的距离就是v到k的最短路径长度）；

　　(3)以k为新考虑的中间点，修改U中各顶点的距离；若从源节点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，

　　则修改顶点u的距离值，修改后的距离值是顶点k的距离加上k到u的距离；

　　(4)重复步骤（2）和（3），直到所有顶点都包含在S中。

　　具体图例与算法执行步骤：（就从A开始，到各节点的最短路径）。

　　重点需要理解这句拗口的”按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度”

　　实际上，Dijkstra 算法是一个排序过程，就上面的例子来说，是根据A到图中其余点的最短路径长度进行排序，路径越短越先被找到，路径越长越靠后才能被找到，要找A到F的最短路径，我们依次找到了

　　A –> C 的最短路径 3

　　A –> C –> B 的最短路径 5

　　A –> C –> D 的最短路径 6

　　A –> C –> E 的最短路径 7

　　A –> C –> D –> F 的最短路径 9

　　这个算法与普兰姆算法十分的相似，所以要先好好的理解普鲁米算法

　　下图就是我在草纸上的的循环过程(如需用图，请与作者联系以取得许可 )

　　其实讲真我不明白为什么这样出来的就一定是最短路径。唉。

　　留待以后解决吧。。

　　>>

　　

#include 'stdio.h' #include 'stdlib.h' #include 'io.h' #include 'time.h'#define OK 1#define TRUE 1#define ERROR 0#define FALSE 0#define MAXEDgE 20#define MAXVEX 20#define INFINITY 65535typedef int Status; /* Status定义函数结果状态代码，如OK等 */ typedef struct{ int vexs[MAXVEX]; int arc[MAXVEX][MAXVEX]; int numVertexes, numEdges;}Mgraph;typedef int Patharc[MAXVEX]; /* 用于存储最短路径下标的数组 */typedef int ShortPathTable[MAXVEX]; /* 用于存储到各点最短路径的权值和 */void CreateMgraph(Mgraph *g){ int i, j; /* 亦可更改程序：printf('请输入边数和顶点数:');*/ g->numEdges=16; g->numVertexes=9; for (i = 0; i < g-="">numVertexes; i++)/* 初始化图 */ { g->vexs[i]=i; } for (i = 0; i < g-="">numVertexes; i++)/* 初始化图 */ { for ( j = 0; j < g-="">numVertexes; j++) { if (i==j) g->arc[i][j]=0; else g->arc[i][j] = g->arc[j][i] = INFINITY; } } g->arc[0][1]=1; g->arc[0][2]=5; g->arc[1][2]=3; g->arc[1][3]=7; g->arc[1][4]=5; g->arc[2][4]=1; g->arc[2][5]=7; g->arc[3][4]=2; g->arc[3][6]=3; g->arc[4][5]=3; g->arc[4][6]=6; g->arc[4][7]=9; g->arc[5][7]=5; g->arc[6][7]=2; g->arc[6][8]=7; g->arc[7][8]=4; for(i = 0; i < g-="">numVertexes; i++) { for(j = i; j < g-="">numVertexes; j++) { g->arc[j][i] =g->arc[i][j]; } }}/* Dijkstra算法： 求v0顶点到其余顶点v的最短路径P[v]，P[v]的值为前驱顶点下标 带权长度D[v] , D[v]表示v0到v的最短路径长度和 P即point：标志，下标； D即 distance 权值，距离。*/ void ShortestPath_Dijkstra(Mgraph g, int v0, Patharc *P, ShortPathTable *D){ int v,w,k,min; /*v代表与顶点相关，w代表与权值相关，以v w 作为循环参量*/ int final[MAXVEX]; /* final[w]=1表示求得顶点v0至vw的最短路径 */ /* 初始化数据 */ for(v=0; v/*因为P，D都是指针，这里解引用他们来做一维数组*/ final[v] = 0; /* final是标志位,有0/1两种状态，=1为最短路径状态 */ (*D)[v] = g.arc[v0][v]; /* 权值都赋上 */ (*P)[v] = 0; /* 初始化路径数组P为0 */ } (*D)[v0] = 0; /* v0至v0路径为0 */ final[v0] = 1; /* v0至v0不需要求路径 */ /* 开始主循环，每次求得v0到某个v顶点的最短路径,注意是 v0(源点) */ for(v = 1; v < g.numvertexes="" ;="" v++)="" {="" min="INFINITY;">/* 当前所知离v0顶点的最近距离 */ for(w = 0; w < g.numvertexes="" ;="" w++)="">/* 寻找离v0最近的顶点 */ { if( !final[w] && (*D)[w] < min)="">/*这是 IF */ { k = w; min = (*D)[w]; /* w顶点离v0顶点更近 */ } } final[k] = 1; /*标志为1，说明 求得了k点到v0的最小路径*/ /* 修正当前最短路径及距离 */ for(w=0; w/*遍历所有节点*/ { /* 如果经过v顶点的路径比现在这条路径的长度短的话 */ if(!final[w] && (min+g.arc[k][w]/* 说明找到了更短的路径，修改D[w]和P[w] */ (*D)[w] = min + g.arc[k][w]; /* 修改当前路径长度 */ (*P)[w] = k; } } }}int main(void){ int i,j,v0; Mgraph g; Patharc P; ShortPathTable D; /* 求某点到其余各点的最短路径 */ v0=0; CreateMgraph(&g); ShortestPath_Dijkstra(g, v0, &P, &D); printf('最短路径倒序如下:\n'); for(i=1;iprintf('v%d - v%d : ',v0,i); j=i; while(P[j]!=0) { printf('%d ',P[j]); j=P[j]; } printf('\n'); } printf('\n源点到各顶点的最短路径长度为:\n'); for(i=1;iprintf('v%d - v%d : %d \n',g.vexs[0],g.vexs[i],D[i]); return 0;}1

　　2

　　3

　　4

　　5

　　6

　　7

　　8

　　9

　　10

　　11

　　12

　　13

　　14

　　15

　　16

　　17

　　18

　　19

　　20

　　21

　　22

　　23

　　24

　　25

　　26

　　27

　　28

　　29

　　30

　　31

　　32

　　33

　　34

　　35

　　36

　　37

　　38

　　39

　　40

　　41

　　42

　　43

　　44

　　45

　　46

　　47

　　48

　　49

　　50

　　51

　　52

　　53

　　54

　　55

　　56

　　57

　　58

　　59

　　60

　　61

　　62

　　63

　　64

　　65

　　66

　　67

　　68

　　69

　　70

　　71

　　72

　　73

　　74

　　75

　　76

　　77

　　78

　　79

　　80

　　81

　　82

　　83

　　84

　　85

　　86

　　87

　　88

　　89

　　90

　　91

　　92

　　93

　　94

　　95

　　96

　　97

　　98

　　99

　　100

　　101

　　102

　　103

　　104

　　105

　　106

　　107

　　108

　　109

　　110

　　111

　　112

　　113

　　114

　　115

　　116

　　117

　　118

　　119

　　120

　　121

　　122

　　123

　　124

　　125

　　126

　　127

　　128

　　129

　　130

　　131

　　132

　　133

　　134

　　135

　　136

　　137

　　138

　　139

　　140

　　141

　　142

　　143

　　144

　　145

　　146

　　147

　　148

　　149

　　150

　　151

　　152

　　153

　　154

　　155

　　156

　　157

　　158

　　159

　　

　　鸣谢：htp://blog.chinaunix.net/uid-26548237-id-3834514.html

　　部分转载自： @梦醒潇湘love —— china unix