1 files changed, 132 insertions, 0 deletions
diff --git a/sem1/algo/mm12/dijkstra.c b/sem1/algo/mm12/dijkstra.c
new file mode 100644
index 0000000..103c700
--- /dev/null
+++ b/sem1/algo/mm12/dijkstra.c
@@ -0,0 +1,132 @@
+#include <stdio.h>
+#include <stdlib.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) {
+	list_item_t *smallest = s->begin;
+
+	// Search
+	list_item_t *i = s->begin;
+	while( i ) {
+		if( 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 && 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_edge(&g, 'a', 'b', 2);
+	graph_edge(&g, 'a', 'f', 1);
+
+	graph_edge(&g, 'b', 'd', 3);
+	graph_edge(&g, 'b', 'c', 4);
+
+	graph_edge(&g, 'd', 'b', 1);
+	graph_edge(&g, 'd', 'e', 8);
+
+	graph_edge(&g, 'c', 'a', 7);
+	graph_edge(&g, 'c', 'd', 7);
+	graph_edge(&g, 'c', 'f', 2);
+
+	graph_edge(&g, 'e', 'c', 2);
+	graph_edge(&g, 'e', 'f', 2);
+
+	dijkstra(&g, g.vertexes['a']);
+
+	graph_to_dot(stdout, &g);
+
+	return 0;
+}