DijkStra算法实现校园地图导航

求解最短路径的迪杰斯特拉算法基本思想：

(1) 设置辅助数组Dist，其中每个分量Dist[k] 表示当前所求得的从源点到其余各顶点 k的最短路径。

(2) 一般情况下，Dist[k] = Min{<源点到顶点 k 的弧上的权值>，<源点到其它顶点的最短路径长度> + <其它顶点到顶点 k 的弧上的权值>};

(3) 首先清除所有点的标号;

(4) 设d[0]=0，其他d[i]=inf;

(5) 循环n次,在所有未标号结点中，选出d值最小的结点x，给结点x标记，对于从x出发的所有边（x，y），更新d[y]= min{d[y], d[x]+w(x,y)}。

算法实现

1. 建立地图

1. 在控制台中，将地图抽象为

1. 根据设计要求和实际需要定义的宏如下

#define M 8//地点数 
#define N 12//路径数 
#define mapRowNum 10//地图行数
#define mapColNum 10//地图列数

1. 定义地图二维数组

//地图二维数组 
static char map[mapRowNum][mapRowNum] = {
    {' ', ' ', ' ', ' ', '0', '*', ' ', ' ', ' ', ' '},
    {' ', ' ', ' ', '*', '*', ' ', '1', ' ', ' ', ' '},
    {' ', ' ', '*', ' ', '2', '*', ' ', '*', ' ', ' '},
    {' ', '*', ' ', ' ', '*', ' ', ' ', ' ', '*', ' '},
    {'*', ' ', ' ', '*', '3', '*', ' ', ' ', ' ', '*'},
    {'*', ' ', '*', ' ', '*', ' ', '*', ' ', ' ', '*'},
    {'4', '*', ' ', ' ', '*', ' ', ' ', '*', '*', '6'},
    {' ', ' ', '*', '*', '5', '*', '*', ' ', ' ', ' '},
    {' ', ' ', ' ', ' ', '*', ' ', ' ', ' ', ' ', ' '},
    {' ', ' ', ' ', ' ', '7', ' ', ' ', ' ', ' ', ' '},
};

1. 定义相邻两点间的距离数组

//相邻两点间的距离数组 
static int dist[3][12] = {
    {0, 0, 0, 1, 1, 2, 3, 3, 3, 4, 5, 5},
    {1, 2, 4, 2, 6, 3, 4, 5, 6, 5, 6, 7},
    {3, 2, 12, 3, 10, 2, 9, 4, 11, 7, 9, 2}
};

1. 定义地点名数组

//地点名 
static char loca[8][8] = {"图书馆", "行远楼", "信南", "四区", "东操", "餐厅", "北操", "宿舍区"};

1. 定义其他数组

int edge[N][N], weight[N], disp[N];
bool visited[N] = {false};
const int inf = 999999;

1. 打印地图和图例的函数

//打印地图和图例 
void printMap() {
    printf("  ");
    for(int i = 0; i < mapRowNum; i++) {
        for(int j = 0; j < mapColNum; j++) {
            printf("%c ", map[i][j]);
        }
        printf("\n  ");
    }
    printf("\n");
    printf("图例：(共8个地点)\n  0-图书馆  1-行远楼  2-信南  3-四区");
    printf("  4-东操  5-餐厅  6-北操  7-宿舍区\n\n");
    printf("各地点间距离：(任意两点间共12条路径)\n  ");
    printf("0-1：3;  0-2：2;  0-4：12;  1-2：3;  1-6：10;  2-3：2;  ");
    printf("3-4：9;  3-5：4;  3-6：11;  4-5：7;  5-6：9;  5-7：2 ");
}

1. 求解最短路径的函数

//求解最短路径 
void calculatePath(){
    int prev[N];//用来标注当前结点的上一个结点，以便输出两点间最短路线
    fill(edge[0], edge[0] + N * N, inf);//注意这里要是N*N，要不然不是全部
    fill(disp, disp + N, inf);
    int start_point;
    cout<<"\n\n请输入起点:";
    cin>>start_point;
    //建立二维距离矩阵 
    for(int i=0; i < N; i++) {
        edge[dist[0][i]][dist[1][i]] = edge[dist[1][i]][dist[0][i]] = dist[2][i];
    }
    for(int i = 0; i < N; i++) {
        prev[i] = i;//初始状态设每个点的前驱为自身
        edge[i][i] = 0;
    }
    //DijkStra算法求解最短路径 
    disp[start_point] = 0;
    for(int i = 0; i < M; i++) {
        int u = -1, min = inf;
        for(int j = 0; j < M; j++) {
            if(visited[j] == false && disp[j] <= min) {
                u = j;
                min = disp[j];
            }
        }
        if(u == -1)    break;
        visited[u] = true;
        for(int v = 0; v < M; v++) {
            if(visited[v] == false && edge[u][v] != inf) {
                if(disp[u] + edge[u][v] < disp[v]) {
                    disp[v] = disp[u] + edge[u][v];
                    prev[v] = u;//prev保存当前结点的上一个节点，以便输出最短路线
                }
            }
        }
    }
    int end_point;//终点
    cout<<"请输入终点:";
    cin>>end_point;
    stack<int> myStack;//最短路径栈 
    //构建最短路径栈 
    int temp = end_point;
    myStack.push(end_point);//先加终点
    while(start_point != temp) {
        temp = prev[temp];
        myStack.push(temp);//注意这里是把当前点的上一个结点放进去，此时换成了temp
    }
    cout<<"\n"<<loca[start_point]<<"("<<start_point<<")"<<" -> "<<loca[end_point];
    cout<<"("<<end_point<<")"<<"的最短距离为: "<<disp[end_point]<< "\n对应的路径为:    ";
    //输出最短路径 
    while(!myStack.empty()) {
        cout<<loca[myStack.top()]<<"("<<myStack.top()<<")";
        myStack.pop();
        if(!myStack.empty())
            cout<<"->";
    }
}

1. 主函数

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
int main() {
    printMap();
    calculatePath();
    return 0;
}

运行结果