문제 설명
기차 또는 버스를 이용할 수 있는 도시 간 최단 경로 DYNAMIC PROGRAMMING (Shortest path between cities that you can use either train or bus DYNAMIC PROGRAMMING)
저를 미치게 만드는 문제가 있습니다!
‑‑이것은 동적 프로그래밍으로 해결되어야 합니다. btw‑‑
저는 80개의 도시가 있고 여행을 시작할 추가 시작 도시가 있습니다. 한 도시에서 이 80개 도시로 가는 최단 경로를 찾아야 합니다. 그러나 문제는 여행자가 버스나 기차를 이용할 수 있다는 것입니다.
입력에서 두 특정 도시 사이에 기차 경로가 있는지, 특정 도시 사이에 버스가 있는지, 이러한 옵션 중 하나를 사용하는 여행자의 평균 이동 시간 및 버스 정류장과 기차역이 모두 있는 경우 도시의 버스 정류장과 기차역 사이의 평균 이동 시간이 제공됩니다. 특정 도시로 여행하는 동안 최대 한 번만 교통 수단을 변경할 수 있습니다.
나는 이 문제를 각 도시가 정점이고 이 구조가 비순환 그래프가 아닐 수 있는 수준으로 추상화할 수 있다고 생각합니다. Bellman‑Ford와 같은 알고리즘이나 O(VE) 시간에 실행되는 다른 알고리즘을 사용할 수 있습니다. 그러나 두 도시 사이에 2개의 가장자리가 있을 수 있습니다. 하나는 버스용이고 다른 하나는 기차용입니다. 그러면 어떻게 처리해야 할지 모르겠습니다. 따라서 재귀는 2개의 매개변수, 지정된 정점 및 해당 도시에 도달하는 최대 모서리 수에 따라 달라집니다. 하지만 여기에는 이 기차‑버스 문제에 대한 또 다른 매개변수가 있는 것 같습니다. 처리 방법을 모르겠습니다. bc. 말씀드린 대로 여행 중 최대 한 번만 교통 수단을 변경할 수 있습니다.
내 관심사는 간단합니다. 여행 내내 운송 옵션을 변경할 수 있는 두 도시가 있는 경우, 낮은 비용으로 인해 첫 번째 가능한 도시에서 교통 수단을 변경하면 가장 낮은 총 비용이 발생하지 않을 수 있습니다. 왜냐하면 두 번째로 가능한 도시에서 교통 수단을 변경하면 첫 번째 도시에서 낮추는 것보다 비용이 더 낮아질 수 있기 때문입니다.
도움을 주시면 감사하겠습니다. 미리 감사드립니다!
참조 솔루션
방법 1:
Let's say you only have the bus option, in order to solve this you can use Dijkstra's algorithm, which is usually used to find a path from single node to another but can be easily modified to find the shortest path to all of the nodes in the graph. We will indeed take each city to be node and each lane to be an edge and we are done :)
Now for the interesting part, when you can switch between train and bus only once. Let's create two graphs, G_b and G_t, where G_t contains only the trains paths and G_b contains only the buses paths, the weights are the travel times. The next step is to connect with one directed edge all the nodes from G_b to the corresponding node in G_t. Create another Copy of this graph but this time connect G_t to G_b.
Now run the Dijkstra's algorithm on these two graphs. When you want to know which time was the shortest to a specific city ‑ take the minimum from all 4 occurences of this city. You can know if we have changed transportation by checking if we changed layer in the graph.
The time complexity is lower than Bellman‑Ford by far since we only ran Dijkstra's algorithm twice. O(E + V log V)
방법 2:
Instead of making each city a node, you can opt to make each bus stop as well as each train stop a node, and have edges between adjacent bus stops and adjacent train stops, as well as between the bus stops and train stops in the same cities. Then you can run some SSSP algorithm, maybe Dijkstra's, which runs much faster than Bellman‑Ford, and works for acyclic graphs (provided there are no negative edges) from the source city.
To ensure you don't change method of transportation more than once, you can add an extra boolean parameter to each state, which marks whether you've changed transportation method at some point previously.
(by plshelpme、Yonlif、aeternalis1)