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
|
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "graph.h"
typedef struct list_item {
vertex_t *v;
struct list_item *next;
struct list_item *prev;
} list_item_t;
typedef struct {
int len;
struct list_item *begin;
struct list_item *end;
} list_t;
void list_push(list_t *s, vertex_t *v) {
// Create
list_item_t *i = malloc(sizeof(list_item_t));
i->next = NULL;
i->prev = NULL;
i->v = v;
// Link
if( s->len == 0 ) {
s->begin = i;
} else {
s->end->next = i;
i->prev = s->end;
}
s->end = i;
s->len++;
}
vertex_t *list_pop_smallest(list_t *s) {
//printf("beginning %s(%d)\n", s->begin->v->ref, s->begin->v->dist);
list_item_t *smallest = s->begin;
// Search
list_item_t *i = s->begin;
while( i ) {
if( smallest->v->dist == -1 || (i->v->dist != -1 && i->v->dist < smallest->v->dist) ) {
smallest = i;
}
i = i->next;
}
if( smallest == s->begin ) {
s->begin = smallest->next;
} else {
smallest->prev->next = smallest->next;
}
if( smallest == s->end ) {
s->end = smallest->prev;
} else {
smallest->next->prev = smallest->prev;
}
vertex_t *v = smallest->v;
free(smallest);
s->len--;
return v;
}
graph_t g;
// Assumes u has an edge to v
void relax(vertex_t *u, vertex_t *v) {
// Get edge between these two guys
edge_t *e = u->adj;
while(e && e->next && strcmp(e->to->ref, v->ref)) {
e = e->next;
}
if( v->dist == -1 || v->dist > (u->dist + e->weight) ) {
v->dist = u->dist + e->weight;
v->p = u;
}
}
void dijkstra(graph_t *g, vertex_t *s) {
list_t list;
list.len = 0;
list.end = list.begin = 0;
s->dist = 0;
{
vertex_t *v = vertex_next(g, NULL);
while( v ) {
list_push(&list, v);
v = vertex_next(g, v);
}
}
while( list.len ) {
vertex_t *u = list_pop_smallest(&list);
edge_t *e = u->adj;
while( e ) {
relax(u, e->to );
e = e->next;
}
}
}
int main() {
graph_from_dot(stdin, &g);
dijkstra(&g, graph_vertex(&g, "0"));
graph_to_dot(stdout, &g);
return 0;
}
|
