Graph/C/Dijkstra.c
void dijkstra(Graph* G, int index) {
    // 准备辅助数组
    int* s = (int*)malloc(sizeof(int) * G -> vexNum);
    int* p = (int*)malloc(sizeof(int) * G -> vexNum);
    int* d = (int*)malloc(sizeof(int) * G -> vexNum);
    // 初始化辅助数组
    for (int i = 0; i < G -> vexNum; i++) {
        if (G -> arcs[index][i] > 0 && G -> arcs[index][i] != MAX) {
            d[i] = G -> arcs[index][i];
            p[i] = index;
        }
        else {
            d[i] = MAX;
            p[i] = -1;
        }
        if (i == index) {
            s[i] = 1;
            d[i] = 0;
        }
        else
            s[i] = 0;
    }
    for (int i = 0; i < G -> vexNum - 1; i++) {
        int index = getMin(d, s, G);
        s[index] = 1;
        for (int j = 0; j < G -> vexNum; j++) {
            if (!s[j] && d[index] + G -> arcs[index][j] < d[j]) {
                d[j] = d[index] + G -> arcs[index][j];
                p[j] = index;
            }
        }
    }
    for (int i = 0; i < G ->vexNum; i++) {
        printf("%d %d %d\n", s[i], p[i], d[i]);
    }
}
/**
 * dijkstra
 * @param G the pointer of graph
 * @param index the index you want to start
 */
dijkstra
@param G the pointer of graph
@param index the index you want to start
dijkstra @param G the pointer of graph @param index the index you want to start
void dijkstra(Graph* G, int index) {
    int* s = (int*)malloc(sizeof(int) * G -> vexNum);
    int* p = (int*)malloc(sizeof(int) * G -> vexNum);
    int* d = (int*)malloc(sizeof(int) * G -> vexNum);
    for (int i = 0; i < G -> vexNum; i++) {
        if (G -> arcs[index][i] > 0 && G -> arcs[index][i] != MAX) {
            d[i] = G -> arcs[index][i];
            p[i] = index;
        }
        else {
            d[i] = MAX;
            p[i] = -1;
        }
        if (i == index) {
            s[i] = 1;
            d[i] = 0;
        }
        else
            s[i] = 0;
    }
    for (int i = 0; i < G -> vexNum - 1; i++) {
        int index = getMin(d, s, G);
        s[index] = 1;
        for (int j = 0; j < G -> vexNum; j++) {
            if (!s[j] && d[index] + G -> arcs[index][j] < d[j]) {
                d[j] = d[index] + G -> arcs[index][j];
                p[j] = index;
            }
        }
    }
    for (int i = 0; i < G ->vexNum; i++) {
        printf("%d %d %d\n", s[i], p[i], d[i]);
    }
}
void dijkstra ( Graph * G , int index ) { int * s = ( int * ) malloc ( sizeof ( int ) * G -> vexNum ) ; int * p = ( int * ) malloc ( sizeof ( int ) * G -> vexNum ) ; int * d = ( int * ) malloc ( sizeof ( int ) * G -> vexNum ) ; for ( int i = 0 ; i < G -> vexNum ; i ++ ) { if ( G -> arcs [ index ] [ i ] > 0 && G -> arcs [ index ] [ i ] != MAX ) { d [ i ] = G -> arcs [ index ] [ i ] ; p [ i ] = index ; } else { d [ i ] = MAX ; p [ i ] = -1 ; } if ( i == index ) { s [ i ] = 1 ; d [ i ] = 0 ; } else s [ i ] = 0 ; } for ( int i = 0 ; i < G -> vexNum - 1 ; i ++ ) { int index = getMin ( d , s , G ) ; s [ index ] = 1 ; for ( int j = 0 ; j < G -> vexNum ; j ++ ) { if ( ! s [ j ] && d [ index ] + G -> arcs [ index ] [ j ] < d [ j ] ) { d [ j ] = d [ index ] + G -> arcs [ index ] [ j ] ; p [ j ] = index ; } } } for ( int i = 0 ; i < G -> vexNum ; i ++ ) { printf ( " \n " , s [ i ] , p [ i ] , d [ i ] ) ; } }
dijkstra
 @param G the pointer of graph
 @param index the index you want to start
dijkstra @param G the pointer of graph @param index the index you want to start
// 准备辅助数组 // 初始化辅助数组