不准访问
- 积分
- 400
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2012-6-20
- 最后登录
- 1970-1-1
|
看到一次就得六分,很有成就感,Yeah! 木有没采用Heap,有空再采用Heap,上周的SCC还没有搞定啊...- #include <stdio.h>
- #include <stdlib.h>
- #undef __test
- //#define __test
- #ifdef __test
- #define MAX 4
- #endif
- #ifndef MAX
- #define MAX 200
- #endif
- struct node
- {
- int label;
- int weight;
- struct node * next;
- };
- void init(struct node *, int);
- void add_edge(int, int, int, struct node*, int);
- struct node graph[MAX + 1];
- int X[MAX + 1], V_X[MAX + 1];
- void dijkstra(int, struct node *, int);
- void read_data(char *, struct node *, int);
- int A[MAX + 1];
- int main(void)
- {
- int x;
- for(x = 0; x <= MAX; x++)
- {
- A[x] = 1000000;
- X[x] = -1;
- V_X[x] = x;
- }
- int length = MAX;
- #ifndef __test
- read_data("D:\\dijkstraData.txt", graph, length);
- #endif
- #ifdef __test
- add_edge(1, 2, 1, graph, length);
- add_edge(1, 3, 4, graph, length);
- add_edge(2, 3, 2, graph, length);
- add_edge(2, 4, 4, graph, length);
- add_edge(3, 4, 3, graph, length);
- add_edge(2, 1, 1, graph, length);
- add_edge(3, 1, 4, graph, length);
- add_edge(3, 2, 2, graph, length);
- add_edge(4, 2, 4, graph, length);
- add_edge(4, 3, 3, graph, length);
- #endif
- dijkstra(1, graph, length);
- #ifdef __test
- int num = 4;
- int shortest[4] = {1, 2, 3, 4};
- #endif
- #ifndef __test
- int num = 10;
- int shortest[10] = {7,37,59,82,99,115,133,165,188,197};
- #endif
- printf("Destinations:");
- for(x = 0; x < num; x++)
- {
- printf("%d,", shortest[x]);
- }
- printf("\n");
- printf("Shortest paths: ");
- for(x = 0; x < num; x++)
- {
- printf("%d,", A[shortest[x]]);
- }
- printf("\n");
- return 0;
- }
- void init(struct node * data, int len)
- {
- int x;
- for(x = 1; x <= len; x++)
- {
- (data + x)->label = x;
- (data + x)->weight = 0;
- (data + x)->next = NULL;
- }
- }
- void add_edge(int origin, int to, int weight, struct node * data, int len)
- {
- if(origin == to)
- {
- printf("Don't allow self loop.\n");
- return;
- }
- else if(origin > len || to > len)
- {
- printf("Impossible edge!\n");
- return;
- }
- struct node * temp = data + origin;
- while(temp->next != NULL)
- {
- if(temp->label == to)
- {
- printf("Edge is existed!\n");
- printf("%d -> %d\n", origin, to);
- return;
- }
- temp = temp->next;
- }
- temp->next = (struct node *)malloc(sizeof(struct node));
- temp->next->label = to;
- temp->next->next = NULL;
- temp->next->weight = weight;
- }
- void dijkstra(int origin, struct node * data, int len)
- {
- X[origin] = origin;
- V_X[origin] = -1;
- A[origin] = 0;
- int x = 1;
- while(x < len)
- {
- int dijkstra_min = -1, to_v = -1;
- int y;
- for(y = 1; y <= len; y++)
- {
- // For every vertex in V.
- if(X[y] != -1)
- {
- //printf("%d ->", X[y]);
- struct node * temp_point = (data + y)->next;
- while(temp_point != NULL)
- {
- //printf("%d ", temp_point->label);
- // Wrong direction. Don't allow it.
- if(V_X[temp_point->label] == -1)
- {
- temp_point = temp_point->next;
- continue;
- }
- // Assume X contain {w,s}, V - X contain {v, t}, and the edge is w->v, s->t
- // then the shortest path is min{A[w] + Lwv, A[s] + Lst].
- if(dijkstra_min == -1)
- {
- dijkstra_min = A[y] + temp_point->weight;
- to_v = temp_point->label;
- }
- else
- {
- if(dijkstra_min > A[y] + temp_point->weight)
- {
- dijkstra_min = A[y] + temp_point->weight;
- to_v = temp_point->label;
- }
- }
- temp_point = temp_point->next;
- }
- }
- }
- if(to_v == -1)
- {
- // Cann't go to other vertex.
- break;
- }
- else
- {
- X[to_v] = to_v;
- V_X[to_v] = -1;
- A[to_v] = dijkstra_min;
- }
- x++;
- }
- }
- void read_data(char * file, struct node * data, int len)
- {
- FILE *fp = fopen(file, "rb");
- while(!feof(fp))
- {
- int origin, to, weight;
- fscanf(fp, "%d", &origin);
- int mark = 1;
- while(mark)
- {
- fscanf(fp, "%d,%d ", &to, &weight);
- add_edge(origin, to, weight, data, len);
- int previous, next;
- next = fgetc(fp);
- if(next == EOF)
- mark = 0;
- else
- {
- fseek(fp, -2, SEEK_CUR);
- previous = fgetc(fp);
- if(previous == '\n' || previous == '\r')
- mark = 0;
- }
- }
- }
- }
复制代码 |
|