贪心算法之Dijkstra算法， 求单源最短路径

1.Dijkstra算法是解决单元最短路径问题的贪心算法。
算法思想：一个顶点属于S当且仅当源到该顶点的最短路径长度已知。初始S中仅含有源。设u是G的某一顶点，
把从源到u且中间只经过S中顶点的录称为从源到u的特殊路径，并用dist数组记录当前每个顶点对应的最短特殊路径长度。
Dijkstra算法每次从V-S中取出具有最短特殊路径长度的顶点u,将u添加到S中，同时对dist数组作必要的修改。一旦S中包含了V中所有顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。

dist[i]：表示当前从源到顶点i的最短特殊路径长度。

2.复杂度：
对于n个顶点e条边的带权有向图，算法复杂度是O(n^2)。

3.代码：

#include <stdio.h>

#define maxnodenum 100
#define maxedgenum 100
#define MAX_VALUE 200
int matrix[maxnodenum][maxnodenum];
int nodes[maxnodenum], dist[maxnodenum], prev[maxnodenum];
int nodenum, edgenum;
static void matrix_init(void);
static void dijkstra(int v);
static void print_dijkstra(int v, int e);
int main(int argc, char **argv)
{ int v, e;

        matrix_init();
        printf("Input source node: ");
        scanf("%d", &v);
        getchar();
        dijkstra(v);
        printf("Input end node: ");
        scanf("%d", &e);
        getchar();
        print_dijkstra(v, e);
        return(0);
}

static void matrix_init(void)
{
        int i, j, row, col, weight;

        printf("Input nodenum and edgenum:\n");
        scanf("%d %d", &nodenum, &edgenum);
        getchar();

        for(i = 1; i <= nodenum; i++){
                for(j = 1; j <= nodenum; j++){
                        matrix[i][j] = MAX_VALUE;
                }
        }

        printf("Input all edges:\n");
        for(i = 0; i < edgenum; i++){
                scanf("%d %d %d", &row, &col, &weight);
                getchar();
                matrix[row][col] = weight;
        }
}

static void dijkstra(int v)
{
        int i, j, u, temp, newdist;

        for(i = 1; i <= nodenum; i++){
                dist[i] = matrix[v][i];
                if((dist[i] == MAX_VALUE)){
                        prev[i] = 0;
                }
                else{
                        prev[i] = v;
                }
        }

        nodes[v] = 1;
        for(i = 1; i < nodenum; i++){
                temp = MAX_VALUE;
                u = v;
                for(j = 1; j <= nodenum; j++){
                        if((!nodes[j]) && (dist[j] < temp)){
                                temp = dist[j];
                                u = j;
                        }
                }
                nodes[u] = 1;
                for(j = 1; j <= nodenum; j++){
                        if((!nodes[j]) && (matrix[u][j] < MAX_VALUE)){
                                newdist = matrix[u][j] + dist[u];
                                if(newdist < dist[j]){
                                        dist[j] = newdist;
                                        prev[j] = u;
                                }
                        }
                }
        }
}

static void print_dijkstra(int v, int e)
{
        int i;

        printf("The shortest path from node %d to node %d is: ", v, e);
        printf("%d", e);
        for(i = e; i != v; i = prev[i]){
                printf("<-%d", prev[i]);
        }
        printf("\n");
}