Chpt5-贪心技术-算法5.4--单源最短路径Dijkstra

求一个加权图的单源最短路径，即每个点到graph[0][0]的距离。

这个问题以前写过，不打算描述太多了。经典的思想啊...

 

#define _GNU_SOURCE
#include

#include
#include
#include

#define MAX_BUFFER 1024
#define MAX_NODE 30

int ** graph = NULL;

 

/*Show Usage*/
void usage(char * prog)
{
        printf("Usage %s [-i inputfile] [-n number of nodes]\n", prog);
        exit(110);
}

 

/*free the space for graph*/

void free_graph(int node_number)
{
        int i;
        if(graph == NULL)
                return;

        for(i = 0; i < node_number; i ++)
        {
                free(graph[i]);
        }
        free(graph);
}

 

/*find the next node form set q*/

int extrace_min(int * q, int node_number, int * dist)
{
        int i, temp = -1, tmp_dist = -1;
        for(i = 0; i < node_number; i ++)
        {
                if(q[i] == i && dist[i] > 0)
                {
                        if(tmp_dist < 0)
                        {
                                temp = i;
                                tmp_dist = dist[i];
                                continue;
                        }
                        if(tmp_dist > dist[i])
                        {
                                temp = i;
                                tmp_dist = dist[i];
                        }
                }
        }
        return temp;
}

 

/*Algorithm*/

void dijkstra(int node_number, int ** mygraph, int * distance, int * previous)
{
        int u, i;
        int num = node_number;
        int * q = (int *)malloc(node_number * sizeof(int));

        for(i = 0; i < node_number; i ++)
        {
                distance[i] = graph[0][i];
                q[i] = i;
                if(distance[i] > 0)
                        previous[i] = 0;
                else
                        previous[i] = -1;
        }

        distance[0] = 0;
        previous[0] = 0;
        q[0] = -1; //node 0 is the source node

        while(num > 1)
        {

                u = extrace_min(q, node_number, distance);
                q[u] = -1;
                for(i = 0; i < node_number; i ++)
                {
                        if(q[i] == i && graph[u][i] > 0)
                        {
                                if(distance[i] > distance[u] + graph[u][i] || distance[i] < 0)
                                {
                                        distance[i] = distance[u] + graph[u][i];
                                        previous[i] = u;
                                }
                        }
                }
                num --;
        }

        free(q);

        printf("Distance: ");
        for(i = 0; i < node_number; i ++)
                printf("%d ", distance[i]);
        printf("\nPrevious: ");
        printf("- ");
        for(i = 1; i < node_number; i ++)
                printf("%d ", previous[i] + 1);
        printf("\n");
}

 

/*Read the input file and initialize the graph*/

void init_graph(FILE * fp, int node_number)
{
        char buf[MAX_BUFFER];
        int i, j;
        char * get;
        char * head;

        graph = (int **)malloc(node_number * sizeof(int *));
        for(i = 0; i < node_number; i ++)
                graph[i] = (int *)malloc(node_number * sizeof(int));

        for(i = 0; i < node_number; i ++)
        {
                if(fgets(buf, MAX_BUFFER, fp) != NULL)
                {
                        head = buf;
                        for(j = 0; j < (node_number -1); j ++)
                        {
                                get = strstr(head, " ");
                                if(get != NULL)
                                        *get = '\0';
                                else
                                {
                                        printf("Error in reading the input file!");
                                        free_graph(node_number);
                                        fclose(fp);
                                        exit(98);
                                }
                                graph[i][j] = atoi(head);
                                head = get + 1;
                        }
                        graph[i][j] = atoi(head);
                }
                else
                {
                        free_graph(node_number);
                        fclose(fp);
                        printf("Invalid input file!\n");
                        exit(99);
                }
        }
        fclose(fp);
}

int main(int argc, char * argv[])
{
        int opt, node_number;
        char * input_file = NULL;
        FILE * fp_input;
        int i, j;
        int * dist;
        int * prev;

        /*Check arguments*/
        if(argc != 5)
                usage(argv[0]);
        while((opt = getopt(argc, argv, "i:n:")) != EOF)
        {
                switch(opt)
                {
                        case 'i':
                                input_file = optarg;
                                break;
                        case 'n':
                                node_number = atoi(optarg);
                                break;
                        default:
                                usage(argv[0]);
                                break;
                }
        }

        if((fp_input = fopen(input_file, "r")) == NULL)
        {
                printf("Can't open the input file!\n");
                exit(99);
        }
        if(node_number > MAX_NODE)
        {
                printf("The max number of nodes is: %d\n", MAX_NODE);
                exit(98);
        }

        init_graph(fp_input, node_number);
        printf("The Graph:\n");
        for(i = 0; i < node_number; i ++)
        {
                for(j = 0; j < node_number; j ++)
                {
                        if(graph[i][j] < 0)
                                printf("* ");
                        else
                                printf("%d ", graph[i][j]);
                }
                printf("\n");
        }

        dist = (int *)malloc(node_number * sizeof(int));
        prev = (int *)malloc(node_number * sizeof(int));
        dijkstra(node_number, graph, dist, prev);
        free_graph(node_number);
        free(dist);
        free(prev);
        return 1;
}