校园导航问题-图的最短路径.cpp

建立一个学校的场所平面图

//求图的最短路径的一个例子.用迪克斯特拉算法.
// 注意:这个题的顶点的编号是从0到MAXPOINT-1 ;
#include<iostream>
#include<vector>
using namespace std;

#define MAXPOINT  10   //最大顶点数
#define limit  32767   //设置没有路径的无穷大

int cost[MAXPOINT][MAXPOINT]={
 {0,10,8,7,15,23,18,35,28,19},
 {10,0,15,33,15,18,21,9,17,13},
 {8,15,0,6,8,14,10,17,20,7},
 {7,33,6,0,9,18,33,12,14,16},
 {15,15,8,9,0,3,8,12,10,13},
 {23,18,14,18,3,0,6,14,10,21},
 {18,21,10,33,8,6,0,5,12,27},
 {35,9,17,12,12,14,5,0,7,10},
 {28,17,20,14,10,10,12,7,0,2},
 {19,13,7,16,13,21,27,10,2,0}
};  //图的各边的权值
  
struct record{
 int allpath;   //从源点到这个点的当前最短距离（权最小）
 vector<int> zuiduanlujing; //记录最短路径上的点.
}; 

int flag[MAXPOINT];   //标志集.记录一个顶点是不是加入在顶点集里.

record lujing[MAXPOINT];


//向顶点集加入指定的顶点.
void shortdjs(int x)
{
 for (int i=0; i<MAXPOINT; i++) //初始化标志集 为0
 {    //初始化各点到点x的最小距离.以及路径.
  flag[i] = 0;
  record temp;
  temp.allpath = cost[x][i];
  if (cost[x][i] != limit)
   temp.zuiduanlujing.push_back(x);
   lujing[i] = temp;
 }

 flag[x] = 1;

 int tempdingdian;
 for (int j=0; j<MAXPOINT; j++)
 {
  record temp;
  int tempallpath = limit;
  for (int k=0; k<MAXPOINT; k++) //寻找顶点集以外的离目标点最近的点
  {
   if (flag[k] == 0 && lujing[k].allpath < tempallpath)
   {
    tempdingdian = k;
    tempallpath = lujing[k].allpath;
   }
  }
  
  flag[tempdingdian] = 1;  //上一步找到的点加入顶点集.

  for (int l=0; l<MAXPOINT; l++) //更新顶点集以外的点离目标点的距离.路径将一起被更新
  {
   if (flag[l] == 0)
   {
    if (lujing[l].allpath > 
     lujing[tempdingdian].allpath + cost[tempdingdian][l])
    {
     lujing[l].allpath = lujing[tempdingdian].allpath +
      cost[tempdingdian][l];
     lujing[l].zuiduanlujing = lujing[tempdingdian].zuiduanlujing;
     lujing[l].zuiduanlujing.push_back(tempdingdian);
    }
   }
  }
 }
}
     
int main()
{
 int m,n;  //n为开始顶点. m为结束顶点
  cout << "以下为地点代码：\n"  ;
  cout << "   0.学校大门   1.一号教学楼   2.试验楼 \n   "       ;
  cout << "3.运动场     4.篮球楼       5.食堂   \n  "  ;
  cout << " 6.胡夫楼     7.读书广场     8.图书馆 \n  "  ;
  cout << " 9.二号教学楼                10.退出\n"      ;
 do
 {
  cout << "\n请输入开始地点代码(顶点编号为0到10):\n";
  cin >> n;
  if(n==10)  break;
  cout << "请输入目标地点代码:\n";
  cin >> m;

  shortdjs(n);

  //输出结果
  cout << "最短路径长度为: " << lujing[m].allpath << endl;
  cout << "经过的地点代码为: " ;
  for (vector<int>::iterator iter= lujing[m].zuiduanlujing.begin();
     iter != lujing[m].zuiduanlujing.end(); iter++)
      cout << *iter << " -> ";
  cout << m << endl;
 } while (1);

 return 0;
}