【C】Dijktra 簡單程式 (Single source shortest path)

1. 宣告

?

1 2 3 4

#define N 100 int Q[N], d[N], pi[N]; int adj_matrix[N][N];

2. 初始化

?

1 2 3 4 5 6 7 8 9

void init(int start){     for (int i=1; i<=N; i++) {         Q[i] = 1;         d[i] = pi[i] = -1;         for (int j=1; j<=N; j++)             adj_matrix[i][j] = -1;     }     d[start] = 0; }

3. Dijkstra

?

1 2 3 4 5 6 7 8 9 10

void dijkstra(){     for (int i=1; i<=N; i++) {         int u = find_min_d();         Q[u] = 0;         for (int v=1; v<=N; v++){             if (adj_matrix[u][v] != -1)                 relax(u, v);         }     } }

4. relax

?

1 2 3 4 5 6

void relax(int u, int v){     if (d[v]>d[u]+adj_matrix[u][v] || d[v]==-1){         d[v] = d[u]+adj_matrix[u][v];         pi[v] = u;     } }

5. find_min_d

?

1 2 3 4 5 6 7 8 9 10

int find_min_d(){     int min_d = 1<<29, node = 1;     for (int i=2; i<=N; i++) {         if (d[i]< min_d && d[i]!=-1 && Q[i]) {             min_d = d[i];             node = i;         }     }     return node; }