0%

datastructure project3

Public Bike Management

Date: 2020-4-29

# Introduction

The programme is aimed to simulate the management of a public bike service. Once a station is empty or full, it must be adjust to the perfect condition, so as all the other stations on the way from PBMC to the problem station.
To choose a best path, we need to consider the following three factors: distance, number of bikes sent from PBMC and number of those sent back. Their priorities are in a descending order in our consideration.
Generally the problem can be seen as an upgraded shortest path problem.

# Algorithm Specification

First we need to store the edge value. For each station, we use a linked list(a[ ]) to store the value of all its edges, and then another linked list(first[ ])to store the head of every node’s edge list.
u, v and w are three variables appear in each of the N lines. We use fuction push to build a single directed edge and function AddEdge to build an undirected edge.

Store Edge Value

Function AddEdge is called N times since there are N edges.

Definition of struct Value

Struct Value contains three factors we need to choose the best path.

Since we need to make some comparison while deciding the best path, all the three factors mentioned before must be considered according to their priorities. Here we reload operator < to simplify our coding. After that we can directly judge between two stations to update our best solution.

As we can see, dis is the factor we give thought to in the first place, followed by take and now.

Dijkstra Algorithm
On the basis of all the work we have done, we can now adapt Dijkstra’s Algorithm to finally complete our job. But before that we must prove the feasibility of the idea.
It is crucial that all the edge values are positive. To illustrate the point, let’s look at an example. Once we have decided $dis_u$ = $dis_v$, then the conclusion is fixed and no extra adjustment shall be made later. That is to say, even if there is another way from u to v, it’s definitely true that $dis_v$+W > $dis_u$ because W is always positive. Thus, whatever the situation, $dis_u$ is still the shorter one.

N is the number of nodes and E is the number of edges. We can see that there is a double-nested loop, so the time complexity of the algorithm is $O(N^2+E)$. The space complexity is $O(N+E)$.

Function Print
Finally we use recursion to output the result.

# Testing Results

Case 1:

A random case to test if the programme is able to work properly.
The expected output is 70 0->2->5->7 0.
Program output is 70 0->2->5->7 0.
Status: Pass.

Case 2:

A random case to test if the programme is able to work properly.
The expected output is 3 0->1->4 0.
Program output is 3 0->1->4 0.
Status: Pass.

Case 3:

A special case to test if the programme can output the path that requires minimum number of bikes taken back.
The expected output is 2 0->1->3->5->7 1.
Program output is 2 0->1->3->5->7 1.
Status: Pass.

Case 4:

A random case to test if the programme is able to work properly(only back).
The expected output is 0 0->2->4 5.
Program output is 0 0->2->4 5.
Status: Pass.

Now we have get a $O(N^2+E)$ algorithm. However, we can do better.
Noticed that we use a for loop to find the best unvisited node. Its time complexity is $O(N)$. We can use heap to optimize it.
If a node doesn’t in the heap, it’s easy. We just push it and its value into the heap. But what if it’s in the heap? We still push it and its value into the heap if this node have better value. Because we will first get this node with better value and we just need to judge if the node pop from heap is visited. Thus, we optimize this process to $O(logN)$. But this project’s N will not be bigger than 500, we can use $O(N^2+E)$ algorithm to solve this problem.
And maybe we can solve this problem in another way. After we find the shortest path, the path will not contain cycles and we will get a DAG. Then we can use top sort to find Answer. Its time complexity is still $O(N^2+E)$ for we still need to find the shortest path.