“Young Scientist”
.
#3 (137)
.
January 2017
5
Mathematics
Top number 1 (Samara) must be connected by edges with all (Table 2).
Table 2.
Weights of edges from the first top
1–2: 1130
1–8: 1280
1–18: 1240
1–26: 2510
1–2: 1220
1–9: 1220
1–19: 1630
1–27: 1860
1–2: 920
1–10: 1210
1–20: 1370
1–28: 1820
1–3: 1130
1–11: 1170
1–20: 1590
1–29: 1910
1–4: 1090
1–12: 1000
1–21: 1420
1–30: 2020
1–4: 1140
1–12: 1220
1–22: 1440
1–31: 2140
1–4: 890
1–13: 1450
1–22: 2030
1–32: 2170
1–5: 900
1–14: 1170
1–23: 1690
1–33: 3250
1–6: 930
1–15: 1120
1–24: 1970
1–33: 2800
1–6: 1000
1–16: 1440
1–25: 1490
1–33: 2950
1–6: 620
1–17: 1340
1–26: 2120
1–7: 930
1–18: 1650
1–26: 2030
And draw edges from all the vertices to the top № 33 (Moscow) (Table 3).
Table 3.
Weights of edges in the last vertex
1–33: 3250
6–33: 2700
16–33: 2400
25–33: 1310
1–33: 2800
6–33: 2770
17–33: 1430
26–33: 890
1–33: 2950
7–33: 2700
18–33: 1810
26–33: 860
2–33: 3250
8–33: 2770
18–33: 1900
26–33: 1200
2–33: 2730
9–33: 2800
19–33: 2400
27–33: 1910
2–33: 2950
10–33: 2590
20–33: 1810
28–33: 1910
3–33: 3250
11–33: 2230
20–33: 1420
29–33: 1660
4–33: 3250
12–33: 2100
21–33: 1520
30–33: 1730
4–33: 2710
12–33: 1950
22–33: 1360
31–33: 1520
4–33: 2950
13–33: 2590
22–33: 1400
32–33: 1770
5–33: 2730
14–33: 2010
23–33: 2100
6–33: 3250
15–33: 3100
24–33: 1840
All data is entered. Bellman — Ford algorithm is used as a way of finding a solution: the search algorithm of finding the
shortest path in a weighted graph [2]. It finds the shortest path from one vertex to all others. Software implementation is made
independently. The pseudo-code of the algorithm is as follows:
for v
∈
V
do d [v]
←
∞
d [s]
←
0
for i
←
1 to |V| — 1
do for (u, v)
∈
E
if d [v] > d [u] + w(u, v) then d [v]
←
d [u]+w(u, v)
return d; [3]
By applying the algorithm to a
graph problem, a solution is that the cheapest trip will cost 2770 rubles (Figure 2). It should
be noted that straight tickets from 1 to 33 vertex cost 3250, 2800 and 2950 respectively.
“Young Scientist”
.
#3 (137)
.
January 2017
7
Mathematics
Bellman-Ford algorithm. Saving
turned a relatively small, but with the increase in the number of people who need to get from
one point to another, its value increases and becomes noticeable, which is important for large companies, as it allows them to
reduce costs and expenses. In the future, the problem will be discussed with respect to transportation.
It is clear that to carry
one kilogram load savings would be small, but with the weight increasing for tens or hundreds of tons, rather large values can
be obtained that companies can save by applying the only representation of the model in the form of a graph and elementary
shortest-path finding algorithm.
References:
1. The site «Russian Railways» — www.rzd.ru access mode.
2. Basaker R., T. Saaty. Finite graphs and networks. — M.: Nauka, 1974. 368 s.
3. Belov V. V., Vorobyov E. M., V. E. Shatalov. Theory grafov. — M., 1976. 392 s.