- /*-----------------------denghui-2015.10.16-----------------------------*/
- #include <iostream>
- using namespace std;
- #define MAX 10001
- int readdata(int Graph[][30], int point[][2]);
- int search(int Graph[][30], int Path[], int point[][2], int n, int start, int end);
- void display(int Path[], int n, int start, int end);
- int main()
- {
- int Graph[30][30], Path[30];
- int point[31][2];
- int n, start, end;
- n = readdata(Graph, point);
- cin >> start >> end;
- int p = search(Graph, Path, point, n, start, end);
- display(Path, n, start, end);
- return 0;
- }
- int readdata(int Graph[][30], int point[][2])
- {
- int n;
- cin >> n;
- int i, j;
- for (i = 0; i < n; ++i) {
- for (j = 0; j < n; ++j) {
- cin >> Graph[i][j];
- }
- }
- return n;
- }
- int search(int Graph[][30], int Path[], int point[][2], int n, int start, int end)
- {
- int i, j, MinPoint;
- for (i = 0; i < n; ++i) { //init for search , add point[start] in set-1
- point[i][0] = Graph[start][i];
- point[i][1] = (start == i);
- Path[i] = start;
- }
- point[n][0] = MAX; // a flag to init the MinPoint
- for (i = 0, MinPoint = n; MinPoint != end; ++i) { // do it n-1 times to add all the points in set-1
- for (j = 0, MinPoint = n; j < n; ++j) { //find the closest point
- if (point[j][1] == 0 && point[j][0] < point[MinPoint][0]) {
- MinPoint = j;
- }
- }
- point[MinPoint][1] = 1; //add the closest point in set-1
- for (j = 0; j < n; ++j) { //update the distance form point[start] to set-others
- if (point[MinPoint][0] + Graph[MinPoint][j] < point[j][0]) {
- point[j][0] = point[MinPoint][0] + Graph[MinPoint][j];
- Path[j] = MinPoint;
- }
- }
- }
- return i - 1;
- }
- void display(int Path[], int n, int start, int end)
- {
- int i;
- int *p = new int[n];
- for (i = 0, p[i] = end; p[i] != start;) { //stack
- ++i;
- p[i] = Path[p[i-1]];
- }
- for (; i >= 0; --i) {
- cout << p[i] << endl;
- }
- }
- //end
- /*==========================Denghui=================================*/
- //该片段来自于http://www.codesnippet.cn/detail/1412201514229.html
来源: http://www.codesnippet.cn/detail/1412201514229.html