[TOC]
# 算法思想
Dijkstra算法是很有代表性的最短路算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。
其基本思想是，設置頂點集合S并不斷地作貪心選擇來擴充這個集合。一個頂點屬于集合S當且僅當從源到該頂點的最短路徑長度已知。
初始時，S中僅含有源。設u是G的某一個頂點，把從源到u且中間只經過S中頂點的路稱為從源到u的特殊路徑，并用數組dist記錄當前每個頂點所對應的最短特殊路徑長度。Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點u，將u添加到S中，同時對數組dist作必要的修改。一旦S包含了所有V中頂點，dist就記錄了從源到所有其它頂點之間的最短路徑長度。
例如：
應用dijkstra算法得到的如下表：
# 分析
### 貪心選擇性質
### 最優子結構
# 代碼實現-1
```
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef struct {
int vertex;
int weight;
} edge_t;
typedef struct {
edge_t **edges;
int edges_len;
int edges_size;
int dist;
int prev;
int visited;
} vertex_t;
typedef struct {
vertex_t **vertices;
int vertices_len;
int vertices_size;
} graph_t;
typedef struct {
int *data;
int *prio;
int *index;
int len;
int size;
} heap_t;
void add_vertex (graph_t *g, int i) {
if (g->vertices_size < i + 1) {
int size = g->vertices_size * 2 > i ? g->vertices_size * 2 : i + 4;
g->vertices = realloc(g->vertices, size * sizeof (vertex_t *));
for (int j = g->vertices_size; j < size; j++)
g->vertices[j] = NULL;
g->vertices_size = size;
}
if (!g->vertices[i]) {
g->vertices[i] = calloc(1, sizeof (vertex_t));
g->vertices_len++;
}
}
void add_edge (graph_t *g, int a, int b, int w) {
a = a - 'a';
b = b - 'a';
add_vertex(g, a);
add_vertex(g, b);
vertex_t *v = g->vertices[a];
if (v->edges_len >= v->edges_size) {
v->edges_size = v->edges_size ? v->edges_size * 2 : 4;
v->edges = realloc(v->edges, v->edges_size * sizeof (edge_t *));
}
edge_t *e = calloc(1, sizeof (edge_t));
e->vertex = b;
e->weight = w;
v->edges[v->edges_len++] = e;
}
heap_t *create_heap (int n) {
heap_t *h = calloc(1, sizeof (heap_t));
h->data = calloc(n + 1, sizeof (int));
h->prio = calloc(n + 1, sizeof (int));
h->index = calloc(n, sizeof (int));
return h;
}
void push_heap (heap_t *h, int v, int p) {
int i = h->index[v] || ++h->len;
int j = i / 2;
while (i > 1) {
if (h->prio[j] < p)
break;
h->data[i] = h->data[j];
h->prio[i] = h->prio[j];
h->index[h->data[i]] = i;
i = j;
j = j / 2;
}
h->data[i] = v;
h->prio[i] = p;
h->index[v] = i;
}
int min (heap_t *h, int i, int j, int k) {
int m = i;
if (j <= h->len && h->prio[j] < h->prio[m])
m = j;
if (k <= h->len && h->prio[k] < h->prio[m])
m = k;
return m;
}
int pop_heap (heap_t *h) {
int v = h->data[1];
h->data[1] = h->data[h->len];
h->prio[1] = h->prio[h->len];
h->index[h->data[1]] = 1;
h->len--;
int i = 1;
while (1) {
int j = min(h, i, 2 * i, 2 * i + 1);
if (j == i)
break;
h->data[i] = h->data[j];
h->prio[i] = h->prio[j];
h->index[h->data[i]] = i;
i = j;
}
h->data[i] = h->data[h->len + 1];
h->prio[i] = h->prio[h->len + 1];
h->index[h->data[i]] = i;
return v;
}
void dijkstra (graph_t *g, int a, int b) {
int i, j;
a = a - 'a';
b = b - 'a';
for (i = 0; i < g->vertices_len; i++) {
vertex_t *v = g->vertices[i];
v->dist = INT_MAX;
v->prev = 0;
v->visited = 0;
}
vertex_t *v = g->vertices[a];
v->dist = 0;
heap_t *h = create_heap(g->vertices_len);
push_heap(h, a, v->dist);
while (h->len) {
i = pop_heap(h);
if (i == b)
break;
v = g->vertices[i];
v->visited = 1;
for (j = 0; j < v->edges_len; j++) {
edge_t *e = v->edges[j];
vertex_t *u = g->vertices[e->vertex];
if (!u->visited && v->dist + e->weight <= u->dist) {
u->prev = i;
u->dist = v->dist + e->weight;
push_heap(h, e->vertex, u->dist);
}
}
}
}
void print_path (graph_t *g, int i) {
int n, j;
vertex_t *v, *u;
i = i - 'a';
v = g->vertices[i];
if (v->dist == INT_MAX) {
printf("no path\n");
return;
}
for (n = 1, u = v; u->dist; u = g->vertices[u->prev], n++)
;
char *path = malloc(n);
path[n - 1] = 'a' + i;
for (j = 0, u = v; u->dist; u = g->vertices[u->prev], j++)
path[n - j - 2] = 'a' + u->prev;
printf("%d %.*s\n", v->dist, n, path);
}
int main () {
graph_t *g = calloc(1, sizeof (graph_t));
add_edge(g, 'a', 'b', 7);
add_edge(g, 'a', 'c', 9);
add_edge(g, 'a', 'f', 14);
add_edge(g, 'b', 'c', 10);
add_edge(g, 'b', 'd', 15);
add_edge(g, 'c', 'd', 11);
add_edge(g, 'c', 'f', 2);
add_edge(g, 'd', 'e', 6);
add_edge(g, 'e', 'f', 9);
dijkstra(g, 'a', 'e');
print_path(g, 'e');
return 0;
}
```
