Форум программистов, компьютерный форум, киберфорум
PHP для начинающих
Войти
Регистрация
Восстановить пароль
 
0 / 0 / 0
Регистрация: 31.03.2018
Сообщений: 2
1

Обьясните код.Как работают и что делают каждые из функции.Программа должна выводить кратчайший путь в графе

30.06.2020, 08:06. Просмотров 98. Ответов 1
Метки html, php (Все метки)

PHP/HTML
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
<!DOCTYPE html>
<html>
    <head>
        <title>Лабораторная работа №4</title>
        <link type="text/css" rel="stylesheet" href="style.css">
    </head>
    <body>
        <h1>Лабораторная работа №4<br>Определение кратчайшего пути в графе</h1>
        <form method = "get" action = "index.php">
            <table>
                <tr>
                    <td align = "center">
                        <h2>Ввод данных</h2>
                    </td>
                </tr>
                <tr>
                    <td align = "center">
                        <textarea name = "graph" type = "text" rows = "9" placeholder = "Весовая матрица"><?=$_GET['graph']?></textarea>
                    </td>
                </tr>
                <tr>
                    <td align = "center">
                        <input name = "need" type = "text" placeholder = "Последняя вершина пути" value = "<?=$_GET['need']?>">
                    </td>
                </tr>
                <tr>
                    <td align = "center">
                        <input class = "go" type = "submit" value = "Найти кратчайший путь">
                    </td>
                </tr>
            </table>
        </form>
        <div class = "code">
            <?php
                $graph = explode(" ", $_GET['graph']);
                $top = $_GET['need'];
                $m = 1;
                $n = 1;
                $quite = 1;
                if (implode("", $graph) == "") {
                    echo "<p>Введите весовую матрицу</p>";
                    $quite--;
                }
                if ($top == "") {
                    echo "<p>Введите вершину, до которой нужно найти кратчайший путь</p>";
                    $quite--;
                }
                if ($graph != "" && $top != "") {
                    findTrue($graph);
                    $max = getMax($graph);
                    $graph = bequite($graph);
                    validation($graph);
                    if ($quite == 1) {
                        write ($graph);
                        $way = findWay($graph);
                        result($way);
                    }
                }
                
                function findTrue($g) {
                    global $m, $n;
                    for ($i = 0; $i < count($g); $i++) {
                        if (strlen($g[$i]) <= 3) {
                            $m++;
                        }
                        else {
                            $i =  count($g);
                        }
                    }
                    for ($i = 0; $i < count($g); $i++) {
                        if (strlen($g[$i]) > 3) {
                            $n++;
                        }
                    }
                    if ($n == 1) {
                        $m--;
                    }
                    if ($m == 1) {
                        $n--;
                    }
                    return $m; return $n;
                }
                
                function getMax($g) {
                    global $n;
                    $max = $g[0];
                    for ($i = 0; $i < count($g); $i++) {
                        if (is_numeric($g[$i]) && $g[$i] > $max) {
                            $max = $g[$i];
                        }
                    }
                    return $max;
                }
                
                function bequite($g) {
                    $k = 0;
                    $may = 0;
                    global $n, $max;
                    for ($i = 0; $i < $n; $i++) {
                        for ($j = 0; $j < $n; $j++) {
                            if (strlen ($g[$k]) <= strlen($max)) {
                                $gr[$i][$j] = $g[$k];
                            }
                            if (strlen ($g[$k]) > strlen($max)) {
                                $gra = $g[$k];
                                $l = 0;
                                while (is_numeric($gra[$l]) || $gra[$l] == "-") {
                                    $gr[$i][$j] = $gr[$i][$j].$gra[$l];
                                    $l++;
                                }
                                $may++;
                            }
                            if ($may >= 1) {
                                if (strlen ($g[$k - 1]) > strlen($max)) {
                                    $gra = $g[$k - 1];
                                    $gr[$i][$j] = "";
 
                                    for ($l = 3; $l < strlen($gra); $l++) {
                                        $gr[$i][$j] = $gr[$i][$j].$gra[$l];
                                    }
                                    $may--;
                                    $k--;
                                }
                            }
                            $k++;
                        }
                    }
                    return $gr;
                }
                
                function validation ($g) {
                    global $n, $m, $top, $quite;
                    if ($n != $m && $n > 0 && $m > 0) {
                        echo "<p>Матрица введена не полностью</p>";
                        $quite--;
                    }
                    if ($top > $n) {
                        echo "<p>Такой вершины в графе нет</p>";
                        $quite--;
                    }
                    for ($i = 0; $i < $n; $i++) {
                        for ($j = 0; $j < $n; $j++) {
                            if (!is_numeric($g[$i][$j]) && $g[$i][$j] != "-") {
                                echo "<p>Вес ребра не может принимать такое значения</p>";
                                $quite--;
                            }
                        }
                    }
                    return $quite;
                }
                
                function write ($g) {
                    echo "Весовая матрица:";
                    global $n;
                    for ($i = 0; $i < $n; $i++) {
                        echo "<br>";
                        for ($j = 0; $j < $n; $j++) {
                            echo $g[$i][$j]." ";
                        }
                    }
                }
                
                function findWay ($g) {
                    global $n, $max;
                    $max++;
                    for ($i = 0; $i < $n; $i++) {
                            $d[$i] = $max;
                            $v[$i] = 1;
                    }
                    $d[0] = 0;
                    do {
                        $mi = $max;
                        $min = $max;
                        for ($i = 0; $i < $n; $i++) {
                            if ($v[$i] == 1 && $d[$i] < $min) {
                                $min = $d[$i];
                                $mi = $i;
                            }
                        }
                        if ($mi != $max) {
                            for ($i = 0; $i < $n; $i++) {
                                if ($g[$mi][$i] > 0 && is_numeric($g[$mi][$i])) {
                                    $t = $min + $g[$mi][$i];
                                    if ($t < $d[$i]) {
                                        $d[$i] = $t;
                                    }
                                }
                            }
                            $v[$mi] = 0;
                        }
                    } while ($mi < $max);
                    return $d;
                }
                    
                function result ($d) {
                    global $n, $top;
                    for ($i = 0; $i <= $n; $i++) {
                        if ($i != 0 && $i == $top) {
                            echo "<br> Кратчайший путь от вершины 1 до вершины ".$top." = ".$d[$i - 1];
                        }
                    }
                }
            ?>
        </div>
    </body>
</html>
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
30.06.2020, 08:06
Ответы с готовыми решениями:

Как найти НЕ Кратчайший путь в графе ?
Мне нужно найти не кратчайший путь в графе от одной вершины к другой, граф неориентированный, задан...

Как найти кратчайший путь на графе?
Задана прямоугольная матрица размера M×N в которой заданы числа. Требуется написать программу,...

Кратчайший путь в графе
Добрый вечер, есть код, но его надо доработать. Не понимаю как и что. Задание: строка ввода # 1: n...

кратчайший путь в графе
делал ли кто нибудь задачу по поиску кратчайшего пути на visual studio 2005? и как его там можно...

1
2171 / 2101 / 509
Регистрация: 27.05.2011
Сообщений: 7,226
30.06.2020, 15:23 2
Думаешь кто-то разберется в коде, где юзаются всякие $g, $mi, $i ? Каша какая-то плохонаписанная
PHP
1
if ($g[$mi][$i] > 0
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
30.06.2020, 15:23

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Кратчайший путь в графе.
Такая задача: Дан ориентированный взвешенный ациклический граф. Требуется найти в нем кратчайший...

Кратчайший путь в графе(Рекурсия)
Я реализовал программу с помощью алгоритма флойда.Препод придрался к тому что я реализовал без...

Найти кратчайший путь в графе
Здравствуйте. Мне необходима помощь в решении курсовой. Необходимо найти кратчайший путь в...

Найдите кратчайший путь в графе
Создайте граф согласно своего варианта в среде С + +, длины путей задайте самостоятельно, найдите...

Кратчайший путь в графе: ошибка в программе
Подскажите, пожалуйста, что не так? Программная реализация алгоритма Форда-Беллмана, поиск...

Найти и вывести кратчайший путь в неориентированном графе.
Условие Найти и вывести кратчайший путь в неориентированном графе, между двумя заданными...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.