活跃农民
- 积分
- 374
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2011-10-6
- 最后登录
- 1970-1-1
|
终于搞定了week 5的编程题。- #include<stdio.h>
- #include<stdlib.h>
- #include<string.h>
- #include<ctype.h>
- #define MAX 200
- const char INFILE[]="dijkstraData.txt";
- struct EDGE {
- long vertex;
- long weight;
- struct EDGE *next;
- };
- void fetch_g(struct EDGE **g) {
- FILE *fp = fopen(INFILE,"r");
- long i,v,w;
- char *token,line[800];
- struct EDGE *node;
- while (fgets(line,800,fp)) {
- token = strtok(line,"\t");
- i = atoi(token);
- g[i] = malloc(sizeof(struct EDGE));
- g[i]->next = NULL;
- while (token = strtok(NULL,"\t\r\n")) {
- sscanf(token,"%ld,%ld",&v,&w);
- node = malloc(sizeof(struct EDGE));
- node->vertex = v;
- node->weight = w;
- node->next = g[i]->next;
- g[i]->next = node;
- }
- }
- }
- void print_g(struct EDGE *g) {
- struct EDGE *node;
- for (node=g; node->next; node=node->next)
- printf("%ld,%ld\t",node->next->vertex,node->next->weight);
- printf("\n");
- }
- void HEAP_DECREASE_KEY(long *q,long i,long *d) {
- long tmp;
- while ((i>1) && (d[q[i/2]]>d[q[i]])) {
- tmp = q[i]; q[i] = q[i/2]; q[i/2] = tmp;
- i = i/2;
- }
- }
- void INIT_SINGLE_SOURCE(struct EDGE **g,long s,long *d,long *p) {
- long i;
- for (i=1; i<=MAX; i++) {
- d[i] = 1000000; // d[i] = INFINITY
- p[i] = -1; // p[i] = NIL
- }
- d[s]=0;
- }
- void MIN_HEAPIFY(long *q,long i,long *d) {
- long left = 2*i, right = 2*i+1, smaller, tmp;
- if ((left<=q[0])&&(q[left]<q[i]))
- smaller = left;
- else
- smaller = i;
- if ((right<=q[0])&&(q[right]<q[smaller]))
- smaller = right;
- if (smaller != i) {
- tmp = q[smaller]; q[smaller] = q[i]; q[i] = tmp;
- MIN_HEAPIFY(q,smaller,d);
- }
- }
- long EXTRACT_MIN(long *q, long *d) {
- long min = q[1];
- q[1] = q[q[0]--];
- MIN_HEAPIFY(q,1,d);
- return min;
- }
- void REFRESH(long u,struct EDGE **g,long *d,long *p) {
- struct EDGE *node;
- long v,w;
- for (node=g[u]; node->next; node=node->next) {
- v = node->next->vertex;
- w = node->next->weight;
- if (d[u]+w<d[v]) {
- d[v]=d[u]+w;
- if (p[v]==(-1))
- p[v]=u;
- else
- REFRESH(v,g,d,p);
- }
- }
- }
- void Dijkstra(struct EDGE **g, long s) {
- long *d,*p,*q,i,u;
- struct EDGE *node;
- d = calloc(MAX+1,sizeof(long));
- p = calloc(MAX+1,sizeof(long));
- q = calloc(MAX+1,sizeof(long));
- q[0] = MAX;
- for (i=1; i<=MAX; i++)
- q[i] = i;
- INIT_SINGLE_SOURCE(g,s,d,p);
- while (q[0]) {
- u=EXTRACT_MIN(q,d);
- REFRESH(u,g,d,p);
- }
- printf("%ld,%ld,%ld,%ld,%ld,%ld,%ld,%ld,%ld,%ld\n",d[7],d[37],d[59],d[82],d[99],d[115],d[133],d[165],d[188],d[197]);
- }
- void main()
- {
- struct EDGE **g;
- g = (struct EDGE **)calloc(MAX+1,sizeof(struct EDGE *));
- fetch_g(g);
- Dijkstra(g,1);
- }
复制代码 有几点想说:
1.这次题目光看视频的话太容易晕了,于是我这次严格按照算法导论上面的伪代码
2.我用heap来存放V[G]\S的所有距离,heap构成一个min-priority queue.
3.每次循环取出heap中最小,然后最后的元素补上,heapify
4.容易忽略的是,如果是一个S指向S的edge使得distance发生改变,
那么必须把head vertex刷新一遍,否则是不对的
5.所以,需要一个p[1..MAX]来判断是否在S中
我相信以上这些视频中应该都提到,但都晕晕呼呼地过去了
只有自己做一遍才能真正理解。
|
|