-
July 10th, 2013, 12:10 PM
#1
How To show The total cost
Hello everyone! I need some help with Dijkstra's algorithm in PHP!
I have created 3 files, the one has input form, the other the algorithm and the last one the results.
Form Html
HTML Code:
<html>
<head>
</head>
<body>
<form action="result.php" method="post">
From :
<input name="x" type="text" value="">
</input><br>
TO :
<input type="text" name="y" value="">
</input><br>
<input type="submit" value="submit">
</form></center>
</body>
</html>
Proses.php
PHP Code:
<?php
function dijkstra($graph_array, $source, $target) {
$vertices = array();
$neighbours = array();
foreach ($graph_array as $edge) {
array_push($vertices, $edge[0], $edge[1]);
$neighbours[$edge[0]][] = array("end" => $edge[1], "cost" => $edge[2]);
}
$vertices = array_unique($vertices);
foreach ($vertices as $vertex) {
$dist[$vertex] = INF;
$previous[$vertex] = NULL;
}
$dist[$source] = 0;
$Q = $vertices;
while (count($Q) > 0) {
// TODO - Find faster way to get minimum
$min = INF;
foreach ($Q as $vertex){
if ($dist[$vertex] < $min) {
$min = $dist[$vertex];
$u = $vertex;
}
}
$Q = array_diff($Q, array($u));
if ($dist[$u] == INF or $u == $target) {
break;
}
if (isset($neighbours[$u])) {
foreach ($neighbours[$u] as $arr) {
$alt = $dist[$u] + $arr["cost"];
if ($alt < $dist[$arr["end"]]) {
$dist[$arr["end"]] = $alt;
$previous[$arr["end"]] = $u;
}
}
}
}
$path = array();
$u = $target;
while (isset($previous[$u])) {
array_unshift($path, $u);
$u = $previous[$u];
}
array_unshift($path, $u);
return $path;
}
$graph_array = array(
array("1", "2", 6),
array("1", "6", 8),
array("1", "3", 4),
array("2", "4", 5),
array("2", "1", 6),
array("2", "3", 2),
array("3", "1", 4),
array("3", "2", 2),
array("3", "5", 2),
array("4", "2", 5),
array("4", "5", 4),
array("5", "3", 2),
array("5", "4", 4),
array("5", "6", 8),
array("6", "1", 8),
array("6", "5", 8),
);
$x1 = $_POST['x'];
$y1 = $_POST['y'];
$path = dijkstra($graph_array, $x1, $y1);
?>
And The result
Result.php
PHP Code:
<?PHP
include("proses.php");
echo "shortest path is: ".implode(" - ", $path)."\n";
?>
When i run the program From 1 to 5, the result is 1 - 3 - 5..
In this situation i want to show like This :
Result
From : 1
To : 5
The Shortest path followed is :
1 - > 3 with cost = 4 meter
3 - > 5 with cost = 2 meter
For total cost = 6 meter
How i get the source to do that
Could anyone help me??
thanks for your time
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|