Practical applications of Graph Algorithms
Graphs are applied widely in our days. They are used in economy, aeronautics,
physics, biology (for analyzing DNA), mathematics and other areas.
This page describes some of the applications of a collection of algorithms (all of them are available in Graph Magics).
Shortest Path:
View algorithm
This is probably the most often used algorithm. It may be applied
in situations where the shortest path between 2 points is needed.
Examples of such applications would be:
-
Computer games - finding the best/shortest route from one point to another.
- Maps - finding the shortest/cheapest path for a car from one city to another, by using
given roads.
- May be used to find the fastest way for a car to get from one point to another
inside a certain city. E.g. satellite navigation system that shows
to drivers which way they should better go.
Minimal Spanning Tree:
View algorithm
- Consider some communications stations (for telephony, cable
television, Internet etc.) and a list of possible connections
between them, having different costs. Find the cheapest way
to connect these stations in a network, so that a station is
connected to any other (directly, or through intermediate stations).
This may be used for example to connect villages to cable television,
or to Internet.
- The same problem, but instead of connecting communications
stations - villages are to be connected with roads.
Eulerian Path/Circuit:
View algorithm
- A postman has to visit a set of streets in order to deliver mails and packages. It is needed to find a path that
starts and ends at the post-office, and that passes through
each street (edge) exactly once. This way the postman will deliver
mails and packages to all streets he has to, and in the same
time will spend minimum efforts/time for the road.
Note that not all graphs have an eulerian circuit.
If needed - the algorithm for Chinese Postman Problem can be used.
Chinese Postman Problem:
- The same problem with the postman as above, but instead of
visiting each street (vertex) exactly once, the postman can
visit them more than once if needed. Thus the path should pass
through each street at least one time and should have the minimum
cost.
- Drawing a circuit with a plotter in a fastest possible way,
or with a minimum cost.
- It may be used to determine the cheapest path for garbage collection, street cleaning,
or snow removal.
- Also applied in routing robots, analysing DNA, and others.
Hamiltonian Path/Circuit:
- The same problem with the postman as above, but instead of
visiting a set of streets (edges), he has to visit each point
(house) exactly once.
Network Flows:
- With Maximum Flow algorithm it is possible to find the most
loaded roads or rails in a certain transportation network, and
also to determine its maximum intensivity. This information
may be then used to improve the traffic situation in those places.
Optimal Graph Coloring:
- This algorithm may be used to color a map with a minimum number of colors.
Graph Median:
View algorithm
- A warehouse should be placed in a city (a region) so that
the sum of shortest distances to all other points (regions)
is minimal. This is useful for lowering the cost of transporting
goods from a warehouase to clients.
Same thing can be considered for selecting the place of a shop, market, office and other buildings.
Graph Center:
View algorithm
- Suppose that a hospital, a fire department, or a police department,
should be placed in a city so that the farthest point
is as close as possible. For example a hospital should be placed
in such a way that an ambulance can get as a fast as possible
to the farthest situated house (point).
|