Re: 有請kming、ntucc、jbs多多關照了

[kming (-85>$Q;Z*:/M;H)]

#include <iostream.h>

#define NUM_NODE 7
#define START 0
#define END 6

void init(int node[NUM_NODE][NUM_NODE]);
void break_init(int node[NUM_NODE][NUM_NODE]);
void findPath(int node[NUM_NODE][NUM_NODE]);
int findNext(int node[NUM_NODE][NUM_NODE], int start);

int main(void) {
        int node[NUM_NODE][NUM_NODE];

        /* initialize */
        init(node);
        cout << "The shortest path from 1 to 7" << endl;
        cout << "=============================" << endl;
        findPath(node);

        /* initialize without edge(3, 4) */
        break_init(node);
        cout << "The shortest path from 1 to 7 without edge(3, 4)" << endl;
        cout << "================================================" << endl;
        findPath(node);

        return(0);
}

void findPath(int node[NUM_NODE][NUM_NODE]) {
        int length;

        /* display the shortest path */
        length = findNext(node, START);
        cout << "Total Loading is: " << length << ".\n\n\n";
}

int findNext(int node[NUM_NODE][NUM_NODE], int start) {
        int i, j, min=100;
        int mid, end;

        for ( i = 0; i < NUM_NODE; i++ ) {
                if ( node[start][i] ) {
                        for ( j = 0; j < NUM_NODE; j++ ) {
                                if ( node[i][j] && j != start &&
                                         (node[start][i] + node[i][j]) < min) {
                                        min = node[start][i] + node[i][j];
                                        mid = i, end = j;
                                }
                        }
                }
        }

        if ( end != END ) {
                cout << start+1 << " -> ";
                return(node[start][mid] + findNext(node, mid));
        }
        else {
                cout << start+1 << " -> " << mid+1 << " -> " << end+1 << endl;
                return(min);
        }
}

void init(int node[NUM_NODE][NUM_NODE]) {
        int i, j;
        for(i=0; i<NUM_NODE; i++)
                for(j=0; j<NUM_NODE; j++)
                        node[i][j] = 0;

        node[0][1] = 3, node[0][2] = 5,
        node[1][0] = 3, node[1][3] = 4, node[1][4] = 4,
        node[2][0] = 5, node[2][3] = 1, node[2][4] = 2,
        node[3][1] = 4, node[3][2] = 1, node[3][5] = 1, node[3][6] = 3,
        node[4][1] = 4, node[4][2] = 2, node[4][5] = 3,
        node[5][3] = 1, node[5][4] = 3, node[5][6] = 1,
        node[6][3] = 3, node[6][5] = 1;
}

void break_init(int node[NUM_NODE][NUM_NODE]) {
        int i, j;
        for(i=0; i<NUM_NODE; i++)
                for(j=0; j<NUM_NODE; j++)
                        node[i][j] = 0;

        node[0][1] = 3, node[0][2] = 5,
        node[1][0] = 3, node[1][3] = 4, node[1][4] = 4,
        node[3][1] = 4, node[3][5] = 1, node[3][6] = 3,
        node[4][1] = 4, node[4][2] = 2, node[4][5] = 3,
        node[5][3] = 1, node[5][4] = 3, node[5][6] = 1,
        node[6][3] = 3, node[6][5] = 1;
}


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.241.8