1

我有一个有向图，其中

1 - From 
2 - To
3 - Start time (HH:mm, casted to integer) 60 => 01:00
4 - difference between endtime, always > 0;



1 2 60 120
1 2 720 125
1 2 900 120
1 3 390 90
1 3 1040 95
2 3 780 180
2 3 1260 180
2 4 240 240
2 4 300 240
2 4 1080 240
3 1 165 90
3 1 1430 90
3 2 1432 180
3 5 1431 249
4 2 1080 240
4 3 720 60

让我们忘记开始时间列，但最简单的算法可能是从 1 到 5 获得 Closest path ，这意味着，通过获得第四列总和较小的最近路径..

提一下：我没有真正的节点制作，我只有关于边缘的信息，我在数组中写

edges[ ''counter'' ] [0] = from;
edges[ ''counter'' ] [1] = to;
edges[ ''counter'' ] [2] = timeToInt(time);
edges[ ''counter'' ] [3] = timeToInt(endTime) - edges[ ''counter'' ] [2];

我听说过Dijkstra 算法，但是如何实现。

4

2 回答 2

0

我误解了规则，我必须尽可能乘坐最近的航班......

// lets find all airports which allows flights from home city and so on..
int min;// minimum value
int minc;// minimal coordinate
int mine;//real position of edge in array
int fakehome = 0;// temprorary position for house
int lastmine = -1;//last position, so can compare times
//cout << timeToInt(begintime);
cout << home << " " << begintime<< endl;
fout << home << " " << begintime<< endl;
while(home != aim)// loop while we havent reached aim/target airport
{
    min = 1440;// 24(hours) * 60 is unreachable value, so 1440 minuts ok
    minc = ports;// max could be count(of airports)
    mine = edges_counter;// array position of edge
    //lastmine = -1;
    for(int i =0;i< edges_counter;i++)
    {
        //if(edges[i][0] == home) cout << edges[i][0] << " " << edges[i][1] <<  " " << edges[i][2] << " " << edges[i][3] << " " << endl;
        if(min > edges[i][2] && edges[i][0] == home && edges[i][4] == 0)
        {
            if(lastmine != -1 && (edges[lastmine][2]+edges[lastmine][3]) < edges[i][2])
            {
                min = edges[i][2];
                minc = edges[i][1];
                mine = i;
                fakehome = edges[i][1];
            }
            else if(lastmine == -1 && timeToInt(saklaiks) < edges[i][2])
            {
                min = edges[i][2];
                minc = edges[i][1];
                mine = i;
                fakehome = edges[i][1];
            }
        }
    }


    if(mine != edges_counter)
    {
        //cout << setw(3) <<  mine << " ";
        intToTime(edges[mine][2],time);
        cout << home << "->" << fakehome << " " << time;
        fout << home << "->" << fakehome << " " << time;
        intToTime((edges[mine][2]+edges[mine][3]), time);
        cout << "-"  << time<< endl;
        fout << "-"  << time<< endl;
        intToTime((edges[mine][2]+edges[mine][3]),begintime);
        home = fakehome;
        edges[mine][4] = 1;
    }
    lastmine = mine;
}

但是有一个问题。。

如果

航班无限循环，无法到达目标。如何检查？

If is given 
3 (how much airports)
1 3 (have to go from 1 to 3)
00:00 (start time)

1 2 01:00-02:00 (from 1 to 2 there is flight that takes 1 hour)
2 1 03:00-04:00 (from 2 to 1 there's also flight that takes 1 hour)
2 3 12:00-13:00 (...)

但是由于 2->1 飞行比 2->3 在打印第一个元素之前知道循环的任何想法更快，因此永远不会达到 2->3，因为它正在打印

1->2 ...
2->1 ...
1->2 ...

等等..我必须打印：“不可能”。

于 2013-11-05T20:15:40.597 回答
0

您的编程语言与此处无关，这纯粹是算法问题。您的一些不错的选择包括：

  • Dijkstra's algorithm，如果所有边的成本都是非负的，就像你的例子一样。Dijkstra 的速度很快，而且相当容易实现。Boost 中有一个实现，谷歌搜索应该会出现很多实现。
  • A*，这实际上是 Dijkstra 的变种。甚至更快，但启发式，因此可以提供不是最好的解决方案，并且可能更难以实施。我强烈建议在实施基本的 Dijkstra 之后，在某个时候实施 A* 作为练习。再一次， A*存在于 Boost 中。
  • Bellman-Ford，如果您需要扩展到负边权重。也出现在 Boost中，只是稍微困难一点。
于 2013-11-05T18:23:58.437 回答