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

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

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

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