利用迪杰斯特拉算法计算最快时间

如果有一个问题,有一张公交车时刻表:

8

Burnie

Deloraine

Devonport

Hobart

Launceston

Oatlands

Queenstown

Swansea

54

0

2 800 845

0 2 1100 1145

0 2 1400 1445

0 2 1700 1745

0 6 800

1100

0 6 1400 1700

1 2 900 945

1 2 1200 1245

1 2 1500 1545

1 2

1800 1845

1 4 1000 1045

1 4 1300 1345

1 4 1600 1645

1 4 1900

1945

2 0 1000 1045

2 0 1300 1345

2 0 1600 1645

2 0 1900 1945

2 1

900 945

2 1 1200 1245

2 1 1500 1545

2 1 1800 1845

3 5 800 900

3 5

1100 1200

3 5 1400 1500

3 5 1700 1800

3 6 900 1400

3 6 1500

2000

4 1 800 845

4 1 1100 1145

4 1 1400 1445

4 1 1700 1745

4 5

800 930

4 5 1100 1230

4 5 1400 1530

4 5 1700 1830

5 3 930 1030

5

3 1230 1330

5 3 1530 1630

5 3 1830 1930

5 4 900 1030

5 4 1200

1330

5 4 1500 1630

5 4 1800 1930

5 7 800 900

5 7 1200 1300

5 7

1600 1700

6 0 1100 1400

6 0 1700 2000

6 3 900 1400

6 3 1500

2000

7 5 900 1000

7 5 1300 1400

7 5 1700 1800

第一个数字代表开始出发的城镇,第二个代表目的地城镇,第三个代表出发时间,第四个代表到达时间。

如果一个城镇到另外一个城镇没有直达车的话,只能选择转车了,要计算出转车的最快时间和路径。

以下是本人编写的代码来实现这个问题,编译器是Visual Studio

2010,已经有town,map,list,bus几个类了。

#include "dijkstra.h"

dijkstra::dijkstra()
{
 departure_tn=NULL;
 m=NULL;
}

dijkstra::dijkstra(town* departure_town,map* mp,list* l)
{
 departure_tn=new town();
 m=new map();
 ls=new list();

 departure_tn=departure_town;
 m=mp;
 ls=l;
}

dijkstra::~dijkstra()
{
 if (departure_tn!=NULL)
 {
  delete departure_tn;
 }

 if (m!=NULL)
 {
  delete m;
 }
}


int dijkstra::get_earliest_arrival_times(int start_time,int departure_town_num,int destination_town_num)
{
 int elst,earliest_times,check=1,min;
 int dep=departure_town_num;
 
 for(int i=0;i<8;i++)
 {
  earliest[i]=10000;
  known[i]=0;
  path[i]=0;
 }

 earliest[dep]=start_time;  //set the shortest arrival time
 elst=dep;
 earliest_times=start_time;

 for(;;)
 {  
  check=1;
  
     min=10000;
  for(int i=0;i<8;i++)
  {
   if(known[i]==0)
   {
    if(min>=earliest[i])
    {
     min=earliest[i];
     elst=i;
    }
   }
  }

  
  for(int i=0;i<8;i++)
  {
   if(known[i]==0)
   {
    check=0;
   }
  }
  if(check)
   break;
   
  
  known[elst]=1;

  for(int i=0;i<8;i++)
  {
   if(strcmp(ls->get_next_direct_bus(earliest[elst],elst,i),"-1")) //if it can get to the vertex directly
   {  
    if(known[i]==0)
    {
     if(atoi(ls->get_next_direct_bus(earliest[elst],elst,i))<earliest[i])
     {
      earliest[i]=atoi(ls->get_next_direct_bus(earliest[elst],elst,i));  //get the earliest arrival time
      path[i]=elst;
     }
    }
   }
  }
 }
 
 if(earliest[destination_town_num]==10000)
 {
  available=0;
  return 0;
 }
 else
 {
  available=1;
  return earliest[destination_town_num];
 }
}


void dijkstra::print_path(int departure_town_num,int destination_town_num)
{
 if(available==0)
  return;
 char* nm1;
 char* nm2;
 nm1=new char[10];
 nm2=new char[10];
 int d=departure_town_num;
 int des=destination_town_num;

 
 if(des!=d)
 {   
  print_path(d,path[des]);

  
  cout<<m->get_towns(path[des])->get_town_name();
  nm1=m->get_towns(path[des])->get_town_name();
  for(int i=0;i<(12-strlen(nm1));i++)
  {
   cout<<" ";
  }

  cout<<m->get_towns(des)->get_town_name();
  nm2=m->get_towns(des)->get_town_name();
  for(int i=0;i<(12-strlen(nm2));i++)
  {
   cout<<" ";
  }
  cout<<ls->get_start_times(earliest[des],path[des],des)<<"  ";
  cout<<ls->get_next_direct_bus(earliest[path[des]],path[des],des)<<endl;
 }
}

Tonitech版权所有 | 转载请注明出处: http://www.tonitech.com/?p=414