32-实战演练

选择背景色：黄橙洋红淡粉水蓝草绿白色选择字体：宋体黑体微软雅黑楷体选择字体大小：小中大特恢复默认

2.5.5　实战演练

//program 2-4
#include <cstdio>
#include <iostream>
#include<cstring>
#include<windows.h>
#include<stack>
using namespace std;
const int N = 100; // 城市的个数可修改
const int INF = 1e7; // 初始化无穷大为10000000
int map[N][N],dist[N],p[N],n,m;//n城市的个数，m为城市间路线的条数
bool flag[N]; //如果flag[i]等于true，说明顶点i已经加入到集合S;否则顶点i属于集合V-S
void Dijkstra(int u)
{
   for(int i=1; i<=n; i++)//①
    {
     dist[i] =map[u][i]; //初始化源点u到其他各个顶点的最短路径长度
     flag[i]=false;
     if(dist[i]==INF)
        p[i]=-1; //源点u到该顶点的路径长度为无穷大，说明顶点i与源点u不相邻
     else
        p[i]=u; //说明顶点i与源点u相邻，设置顶点i的前驱p[i]=u
     }
    dist[u] = 0;
    flag[u]=true;   //初始时，集合S中只有一个元素：源点u
    for(int i=1; i<=n; i++)//②
     {
         int temp = INF,t = u;
         for(int j=1; j<=n; j++) //③在集合V-S中寻找距离源点u最近的顶点t
           if(!flag[j]&&dist[j]<temp)
             {
              t=j;
              temp=dist[j];
             }
           if(t==u) return ; //找不到t，跳出循环
           flag[t]= true;  //否则，将t加入集合
           for(int j=1;j<=n;j++)//④//更新集合V-S中与t邻接的顶点到源点u的距离
             if(!flag[j]&& map[t][j]<INF)//!s[j]表示j在V-S中  
                if(dist[j]>(dist[t]+map[t][j]))
                 {
                   dist[j]=dist[t]+map[t][j] ;
                   p[j]=t ;
                 }
             }
     }
     int main()
     {
             int u,v,w,st;
             system("color 0d");
             cout << "请输入城市的个数："<<endl;
             cin >> n;
             cout << "请输入城市之间的路线的个数："<<endl;
             cin >>m;
             cout << "请输入城市之间的路线以及距离："<<endl;
             for(int i=1;i<=n;i++)//初始化图的邻接矩阵
               for(int j=1;j<=n;j++)
               {
                   map[i][j]=INF;//初始化邻接矩阵为无穷大
               }
             while(m--)
             {
               cin >> u >> v >> w;
               map[u][v] =min(map[u][v],w); //邻接矩阵储存，保留最小的距离
             }
             cout <<"请输入小明所在的位置："<<endl; ;
             cin >> st;
             Dijkstra(st);
             cout <<"小明所在的位置："<<st<<endl;
             for(int i=1;i<=n;i++){
                   cout <<"小明："<<st<<" - "<<"要去的位置："<<i<<endl;
                   if(dist[i] == INF)
                      cout << "sorry,无路可达"<<endl;
                   else
                      cout << "最短距离为:"<<dist[i]<<endl;
             }
             return 0;
   }

算法实现和测试

（1）运行环境

Code::Blocks

（2）输入

请输入城市的个数：
5
请输入城市之间的路线的个数：
11
请输入城市之间的路线以及距离：
1 5 12
5 1 8
1 2 16
2 1 29
5 2 32
2 4 13
4 2 27
1 3 15
3 1 21
3 4 7
4 3 19
请输入小明所在的位置：
5

（3）输出

小明所在的位置：5
小明:5 - 要去的位置:1 最短距离为：8
小明:5 - 要去的位置:2 最短距离为：24
小明:5 - 要去的位置:3 最短距离为：23
小明:5 - 要去的位置:4 最短距离为：30
小明:5 - 要去的位置:5 最短距离为：0

想一想：因为我们在程序中使用p[]数组记录了最短路径上每一个结点的前驱，因此除了显示最短距离外，还可以显示最短路径上经过了哪些城市，可以增加一段程序逆向找到该最短路径上的城市序列。

void findpath(int u)
{
  int x;
  stack<int>s;//利用C++自带的函数创建一个栈s，需要程序头部引入#include<stack>
  cout<<"源点为："<<u<<endl;
  for(int i=1;i<=n;i++)
  {
    x=p[i];
    while(x!=-1)
    {
      s.push(x);//将前驱依次压入栈中
      x=p[x];
    }
    cout<<"源点到其他各顶点最短路径为：";
    while(!s.empty())
    {
      cout<<s.top()<<"--";//依次取栈顶元素
      s.pop();//出栈
    }
    cout<<i<<";最短距离为："<<dist[i]<<endl;
  }
}

只需要在主函数末尾调用该函数：

findpath(st);//主函数中st为源点

输出结果如下。

源点为：5
源点到其他各顶点最短路径为：5--1；最短距离为：8
源点到其他各顶点最短路径为：5--1--2；最短距离为：24
源点到其他各顶点最短路径为：5--1--3；最短距离为：23
源点到其他各顶点最短路径为：5--1--3--4；最短距离为：30
源点到其他各顶点最短路径为：5；最短距离为：0

Previous 上一篇本节目录 Next 下一篇

32-实战演练

2.5.5 实战演练

2.5.5　实战演练