c语言实现Dijkstra算法

1.源码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

#define MAX_POINT_NUMBER 5002
#define DIST_INF 1e7

typedef struct {
    int a;
    int b;
} Edge;

typedef struct {
    int pmp[MAX_POINT_NUMBER];
    int number;
    int numedge;
    int curedge;
    int *points;
    Edge *edges;
    int *dist;
    int *p;
    char *flag;
    int **paths;
} Graph;

Graph *graph_new()
{
    Graph *g = (Graph *)malloc(sizeof(Graph));
    int i;

    memset(g, 0x00, sizeof(Graph));

    for(i=0; i<MAX_POINT_NUMBER; i++)
    {
        g->pmp[i] = -1;
    }

    return g;
}

void graph_free(Graph *g)
{
    int i;

    if(g->points)
    {
        free(g->points);

        g->points = NULL;
    }

    if(g->edges)
    {
        free(g->edges);

        g->edges = NULL;
    }

    if(g->dist)
    {
        free(g->dist);

        g->dist = NULL;
    }

    if(g->p)
    {
        free(g->p);

        g->p = NULL;
    }

    if(g->flag)
    {
        free(g->flag);

        g->flag = NULL;
    }

    if(g->paths)
    {
        for(i=0; i<g->number; i++)
        {
            if(g->paths[i])
            {
                free(g->paths[i]);

                g->paths[i] = NULL;
            }
        }
    }

    g->number = 0;
}

void graph_create_edge(Graph *g, int m)
{
    g->numedge = m;
    g->edges = (Edge *)malloc(m*sizeof(Edge));
}

void graph_add_edge(Graph *g, int x, int y)
{
    g->edges[g->curedge].a = x - 1;
    g->edges[g->curedge].b = y - 1;

    g->curedge++;

    g->pmp[x-1] = 0;
    g->pmp[y-1] = 0;
}

static void graph_init_point_and_edge(Graph *g)
{
    int i, j;

    g->number = 0;

    for(i=0; i<MAX_POINT_NUMBER; i++)
    {
        if(g->pmp[i] == 0)
        {
            g->number++;
        }
    }

    g->paths = (int **)malloc(g->number*sizeof(int *));
    g->points = (int *)malloc(g->number*sizeof(int));

    g->number = 0;

    for(i=0; i<MAX_POINT_NUMBER; i++)
    {
        if(g->pmp[i] == 0)
        {
            g->pmp[i] = g->number;

            g->points[g->number] = i;

            g->number++;
        }
    }

    for(i=0; i<g->number; i++)
    {
        g->paths[i] = (int *)malloc(g->number*sizeof(int));

        for(j=0; j<g->number; j++)
        {
            g->paths[i][j] = DIST_INF;
        }
    }

    for(i=0; i<g->numedge; i++)
    {
        g->paths[g->pmp[g->edges[i].a]][g->pmp[g->edges[i].b]] = 1;
        g->paths[g->pmp[g->edges[i].b]][g->pmp[g->edges[i].a]] = 1;
    }

    g->dist = (int *)malloc(g->number*sizeof(int));
    g->p = (int *)malloc(g->number*sizeof(int));
    g->flag = (char *)malloc(g->number*sizeof(char));

    for(i=0; i<g->number; i++)
    {
        g->dist[i] = DIST_INF;
        g->p[i] = -1;
    }
}

void graph_Dijkstra(Graph *g, int u)
{
    int i = 0;
    int j = 0;

    graph_init_point_and_edge(g);

    u = g->pmp[u];

    if(u < 0)
    {
        return;
    }

    for(i=0; i<g->number; i++)
    {
        g->dist[i] = g->paths[u][i];
        g->flag[i] = 0;

        if(g->dist[i] == DIST_INF)
        {
            g->p[i] = -1;
        }
        else
        {
            g->p[i] = u;
        }
    }

    g->dist[u] = 0;
    g->flag[u] = 1;

    for(i=0; i<g->number; i++)
    {
        int temp = DIST_INF;
        int t = u;

        for(j=0; j<g->number; j++)
        {
            if(!g->flag[j] && g->dist[j] < temp)
            {
                t = j;
                temp = g->dist[j];
            }
        }

        if(t == u) return;

        g->flag[t] = 1;

        for(j=0; j<g->number; j++)
        {
            if(!g->flag[j] && g->paths[t][j] < g->number)
            {
                if(g->dist[j] > g->dist[t] + g->paths[t][j])
                {
                    g->dist[j] = g->dist[t] + g->paths[t][j];

                    g->p[j] = t;
                }
            }
        }
    }
}

int graph_get_min_dist(Graph *g, int u)
{
    u = g->pmp[u];

    if(u < 0)
    {
        return -1;
    }

    if(g->dist[u] != DIST_INF)
    {
        return g->dist[u];
    }
    else
    {
        return -1;
    }
}

int main()
{
    Graph *g = graph_new();
    int n, m;
    int a, b;
    int i;

    scanf("%d %d", &n, &m);

    if(n <= 0 || m <= 0)
    {
        return -1;
    }

    graph_create_edge(g, m);

    for(i=0; i<m; i++)
    {
        a = -1;
        b = -1;

        scanf("%d %d", &a, &b);

        if(a < 1 || b < 1)
        {
            continue;
        }

        graph_add_edge(g, a, b);
    }

    graph_Dijkstra(g, 0);

    printf("%d\n", graph_get_min_dist(g, n-1));

    graph_free(g);

    return 0;
}

2.编译源码

$ gcc -o test test.c -std=c89

3.运行及其结果

$ ./test
4 4
1 2
2 4
3 4
3 1
2