Finding a path from start to end by traversing a graph
I am currently doing a school assignment that wants us to model a bus route map using graphs (undirected), where the edges represent roads which has labels set to the bus route letter (one road may have have bus a, but another may have bus b) and the nodes represent intersections, dead end or the start and end locations. The map is in a rectangular/square grid format, so the maximum number of incident edges a node can have is 4 (meaning the intersection has 4 roads connected to it).
I have implemented the Node, Edge and Graph classes and also managed to add all the edges and nodes required to a graph that represent a sample map. I now have to write a method that uses a Iterator that stores the all the incident edges of a node and a integer value representing how many bus changes are allowed, and traverse through the graph to find ONE path that leads from the start node to the end node without using more bus changes than the specified. Then return a Iterator that stores all the nodes passed on the path from start to end.
This is what I have so far for the method (unfinished as I am stuck):
public Iterator<GraphNode> trip() throws GraphException {
GraphNode startNode = new GraphNode(startLoc); //Creates the starting node.
listOfNodes.add(startNode); //Adds the starting node to the list of nodes that will be the solution.
startNode.setMark(true); //Marks the starting node as true, meaning it has been visited.
pathForEveryNode(graph.incidentEdges(startNode)); //Uses the custom method to find where to go next.
return listOfNodes.iterator(); //Returns the iterator that stores the solution nodes.
}
private List<GraphNode> pathForEveryNode (Iterator<GraphEdge> incidentEdges) throws GraphException {
//This checks if the current node has incident edges or not, if not, then null is returned.
if (incidentEdges == null) {
return null;
} else {
//If the current node does have incident nodes, check the first edge first.
while (incidentEdges.hasNext()) {
tryAgain:{ GraphEdge nextEdge = incidentEdges.next(); //The is the first edge to be checked.
GraphNode endNode = nextEdge.secondEndpoint(); //This is the second end point of the current edge.
/*
* Checks if the current edge and one of the edges connected to the second end point has
* the same bus route set. If not, then the number of changes needs to be checked, if it is,
* then add the second end point to the array list and move to the next set of incident edges.
*/
listOfNodes.add(endNode); //Adds the second end point to the array list.
endNode.setMark(true); //Marks the second end point as true, meaning it has been visited.
tryAgain2:{GraphEdge Snode = graph.incidentEdges(endNode).next();
if (nextEdge.getBusLine() != Snode.getBusLine()) {
/*
* If the number of changes left is larger or equal to 1, it is decreased by 1. Otherwise,
* there is not enough changes left, so back track to the beginning and try the next edge available.
*/
if (kNumOfChanges >= 1) {
kNumOfChanges--;
listOfNodes.add(Snode.secondEndpoint()); //Adds the second end point to the array list.
Snode.secondEndpoint().setMark(true); //Marks the second end point as true, meaning it has been visited.
} else if(kNumOfChanges == 0 && graph.incidentEdges(endNode).hasNext()){ //If the number of changes available or remaining is 0:
break tryAgain2; //Try a different edge connecting to the endNode.
} else if(kNumOfChanges == 0 && !graph.incidentEdges(endNode).hasNext()) {
listOfNodes.remove(endNode); //So the node is removed.
endNode.setMark(false); //Marks the second end point to false, meaning it has not been visited.
break tryAgain; //Try a different incident edge.
}
} else {
listOfNodes.add(Snode.secondEndpoint()); //Adds the second end point to the array list.
Snode.secondEndpoint().setMark(true); //Marks the second end point as true, meaning it has been visited.
}
//If the second end point of the current node is the ending node, return the array list and end the program.
if (Snode.secondEndpoint().getName() == endLoc) {
return listOfNodes;
/*
* If it is not the ending node, check if all of its edges leads to an unmarked node (nodes that has not been visited).
* If there are no nodes that is unmarked (deadend), then this current node doesn't lead any where, so remove it from the
* array list.
*/
} else if (pathForEveryNode(allPathPossibilitiesOneNode(graph.incidentEdges(Snode.secondEndpoint()))) == null) {
listOfNodes.remove(Snode.secondEndpoint()); //remove the current node from the array list.
Snode.secondEndpoint().setMark(false); //Marks the current node to be false, meaning it has not been visited.
listOfNodes.remove(endNode); //So the node is removed.
endNode.setMark(false); //Marks the second end point to false, meaning it has not been visited.
if (kNumOfChanges > 1) {
kNumOfChanges++;
}
}
//Checks if the array list contains the ending node, if it does, then return the array list. Otherwise, return null.
boolean endLocInArray = false;
for(int i = 0; i < listOfNodes.size(); i++) {
if (listOfNodes.get(i).getName() == endLoc) {
endLocInArray = true;
break;
}
}
if(endLocInArray == true) {
return listOfNodes;
}
}}
}
}
return null;
}
and a helper method that checks if the second end point has already been visited or not:
private Iterator<GraphEdge> allPathPossibilitiesOneNode(Iterator<GraphEdge> PossibilitiesIterator) {
List<GraphEdge> allPathPossibilities = new ArrayList<GraphEdge>(); //Initializes the array list that will store the edges.
//This loop goes through all the incident edges connecting to the current node.
while (PossibilitiesIterator.hasNext()) {
GraphEdge currentEdge = PossibilitiesIterator.next(); //The first incident edge.
//This checks if the second end point (next intersection) is marked or not, if not, then add it to the array list.
if (currentEdge.secondEndpoint().getMark() == false) {
allPathPossibilities.add(currentEdge);
}
}
//Return the iterator is the array list is not empty, otherwise return null.
if (!allPathPossibilities.isEmpty()) {
return allPathPossibilities.iterator();
} else {
return null;
}
}
It's supposed to compare the busLine labels of the edge connected to the first node (firstEndPoint) to the edge connected to the secondEndPoint of the first edge to see if the bus routes are the same, if they are not the same then check whether there are enough bus changes left.
What I have so far does run without errors, but the solution printed out is already an empty list, even though it should not be.
We just started the topic on graphs, and is for an assignment.
Edit: example graph and solution:
The path for this map route is 0,1,5,6,10 for the nodes if 1 bus change is allowed.
java graph-traversal undirected-graph
asked Nov 28 '18 at 21:21
PengibabyPengibaby
946
|
show 1 more comment
I am currently doing a school assignment that wants us to model a bus route map using graphs (undirected), where the edges represent roads which has labels set to the bus route letter (one road may have have bus a, but another may have bus b) and the nodes represent intersections, dead end or the start and end locations. The map is in a rectangular/square grid format, so the maximum number of incident edges a node can have is 4 (meaning the intersection has 4 roads connected to it).
I have implemented the Node, Edge and Graph classes and also managed to add all the edges and nodes required to a graph that represent a sample map. I now have to write a method that uses a Iterator that stores the all the incident edges of a node and a integer value representing how many bus changes are allowed, and traverse through the graph to find ONE path that leads from the start node to the end node without using more bus changes than the specified. Then return a Iterator that stores all the nodes passed on the path from start to end.
This is what I have so far for the method (unfinished as I am stuck):
public Iterator<GraphNode> trip() throws GraphException {
GraphNode startNode = new GraphNode(startLoc); //Creates the starting node.
listOfNodes.add(startNode); //Adds the starting node to the list of nodes that will be the solution.
startNode.setMark(true); //Marks the starting node as true, meaning it has been visited.
pathForEveryNode(graph.incidentEdges(startNode)); //Uses the custom method to find where to go next.
return listOfNodes.iterator(); //Returns the iterator that stores the solution nodes.
}
private List<GraphNode> pathForEveryNode (Iterator<GraphEdge> incidentEdges) throws GraphException {
//This checks if the current node has incident edges or not, if not, then null is returned.
if (incidentEdges == null) {
return null;
} else {
//If the current node does have incident nodes, check the first edge first.
while (incidentEdges.hasNext()) {
tryAgain:{ GraphEdge nextEdge = incidentEdges.next(); //The is the first edge to be checked.
GraphNode endNode = nextEdge.secondEndpoint(); //This is the second end point of the current edge.
/*
* Checks if the current edge and one of the edges connected to the second end point has
* the same bus route set. If not, then the number of changes needs to be checked, if it is,
* then add the second end point to the array list and move to the next set of incident edges.
*/
listOfNodes.add(endNode); //Adds the second end point to the array list.
endNode.setMark(true); //Marks the second end point as true, meaning it has been visited.
tryAgain2:{GraphEdge Snode = graph.incidentEdges(endNode).next();
if (nextEdge.getBusLine() != Snode.getBusLine()) {
/*
* If the number of changes left is larger or equal to 1, it is decreased by 1. Otherwise,
* there is not enough changes left, so back track to the beginning and try the next edge available.
*/
if (kNumOfChanges >= 1) {
kNumOfChanges--;
listOfNodes.add(Snode.secondEndpoint()); //Adds the second end point to the array list.
Snode.secondEndpoint().setMark(true); //Marks the second end point as true, meaning it has been visited.
} else if(kNumOfChanges == 0 && graph.incidentEdges(endNode).hasNext()){ //If the number of changes available or remaining is 0:
break tryAgain2; //Try a different edge connecting to the endNode.
} else if(kNumOfChanges == 0 && !graph.incidentEdges(endNode).hasNext()) {
listOfNodes.remove(endNode); //So the node is removed.
endNode.setMark(false); //Marks the second end point to false, meaning it has not been visited.
break tryAgain; //Try a different incident edge.
}
} else {
listOfNodes.add(Snode.secondEndpoint()); //Adds the second end point to the array list.
Snode.secondEndpoint().setMark(true); //Marks the second end point as true, meaning it has been visited.
}
//If the second end point of the current node is the ending node, return the array list and end the program.
if (Snode.secondEndpoint().getName() == endLoc) {
return listOfNodes;
/*
* If it is not the ending node, check if all of its edges leads to an unmarked node (nodes that has not been visited).
* If there are no nodes that is unmarked (deadend), then this current node doesn't lead any where, so remove it from the
* array list.
*/
} else if (pathForEveryNode(allPathPossibilitiesOneNode(graph.incidentEdges(Snode.secondEndpoint()))) == null) {
listOfNodes.remove(Snode.secondEndpoint()); //remove the current node from the array list.
Snode.secondEndpoint().setMark(false); //Marks the current node to be false, meaning it has not been visited.
listOfNodes.remove(endNode); //So the node is removed.
endNode.setMark(false); //Marks the second end point to false, meaning it has not been visited.
if (kNumOfChanges > 1) {
kNumOfChanges++;
}
}
//Checks if the array list contains the ending node, if it does, then return the array list. Otherwise, return null.
boolean endLocInArray = false;
for(int i = 0; i < listOfNodes.size(); i++) {
if (listOfNodes.get(i).getName() == endLoc) {
endLocInArray = true;
break;
}
}
if(endLocInArray == true) {
return listOfNodes;
}
}}
}
}
return null;
}
and a helper method that checks if the second end point has already been visited or not:
private Iterator<GraphEdge> allPathPossibilitiesOneNode(Iterator<GraphEdge> PossibilitiesIterator) {
List<GraphEdge> allPathPossibilities = new ArrayList<GraphEdge>(); //Initializes the array list that will store the edges.
//This loop goes through all the incident edges connecting to the current node.
while (PossibilitiesIterator.hasNext()) {
GraphEdge currentEdge = PossibilitiesIterator.next(); //The first incident edge.
//This checks if the second end point (next intersection) is marked or not, if not, then add it to the array list.
if (currentEdge.secondEndpoint().getMark() == false) {
allPathPossibilities.add(currentEdge);
}
}
//Return the iterator is the array list is not empty, otherwise return null.
if (!allPathPossibilities.isEmpty()) {
return allPathPossibilities.iterator();
} else {
return null;
}
}
It's supposed to compare the busLine labels of the edge connected to the first node (firstEndPoint) to the edge connected to the secondEndPoint of the first edge to see if the bus routes are the same, if they are not the same then check whether there are enough bus changes left.
What I have so far does run without errors, but the solution printed out is already an empty list, even though it should not be.
We just started the topic on graphs, and is for an assignment.
Edit: example graph and solution:
The path for this map route is 0,1,5,6,10 for the nodes if 1 bus change is allowed.
java graph-traversal undirected-graph
asked Nov 28 '18 at 21:21
PengibabyPengibaby
946
Can you add an example graph and an example path through it? Will be very helpful
– mettleap
Nov 28 '18 at 21:28
Thank you for your reply! I have edited the original post with a image of a graph and the solution/path for that graph.
– Pengibaby
Nov 28 '18 at 21:32
read about Dijkstra's algorithm.
– user1373164
Nov 28 '18 at 21:34
Your question says the graphs are undirected and have no cycles, but your example has a cycle actually 2->3->7->6->2
– mettleap
Nov 28 '18 at 21:38
The solution we create cannot have cycles, which is the specification of the assignment. This graph was created using a file provided by the school.
– Pengibaby
Nov 28 '18 at 21:55
|
show 1 more comment
I am currently doing a school assignment that wants us to model a bus route map using graphs (undirected), where the edges represent roads which has labels set to the bus route letter (one road may have have bus a, but another may have bus b) and the nodes represent intersections, dead end or the start and end locations. The map is in a rectangular/square grid format, so the maximum number of incident edges a node can have is 4 (meaning the intersection has 4 roads connected to it).
I have implemented the Node, Edge and Graph classes and also managed to add all the edges and nodes required to a graph that represent a sample map. I now have to write a method that uses a Iterator that stores the all the incident edges of a node and a integer value representing how many bus changes are allowed, and traverse through the graph to find ONE path that leads from the start node to the end node without using more bus changes than the specified. Then return a Iterator that stores all the nodes passed on the path from start to end.
This is what I have so far for the method (unfinished as I am stuck):
public Iterator<GraphNode> trip() throws GraphException {
GraphNode startNode = new GraphNode(startLoc); //Creates the starting node.
listOfNodes.add(startNode); //Adds the starting node to the list of nodes that will be the solution.
startNode.setMark(true); //Marks the starting node as true, meaning it has been visited.
pathForEveryNode(graph.incidentEdges(startNode)); //Uses the custom method to find where to go next.
return listOfNodes.iterator(); //Returns the iterator that stores the solution nodes.
}
private List<GraphNode> pathForEveryNode (Iterator<GraphEdge> incidentEdges) throws GraphException {
//This checks if the current node has incident edges or not, if not, then null is returned.
if (incidentEdges == null) {
return null;
} else {
//If the current node does have incident nodes, check the first edge first.
while (incidentEdges.hasNext()) {
tryAgain:{ GraphEdge nextEdge = incidentEdges.next(); //The is the first edge to be checked.
GraphNode endNode = nextEdge.secondEndpoint(); //This is the second end point of the current edge.
/*
* Checks if the current edge and one of the edges connected to the second end point has
* the same bus route set. If not, then the number of changes needs to be checked, if it is,
* then add the second end point to the array list and move to the next set of incident edges.
*/
listOfNodes.add(endNode); //Adds the second end point to the array list.
endNode.setMark(true); //Marks the second end point as true, meaning it has been visited.
tryAgain2:{GraphEdge Snode = graph.incidentEdges(endNode).next();
if (nextEdge.getBusLine() != Snode.getBusLine()) {
/*
* If the number of changes left is larger or equal to 1, it is decreased by 1. Otherwise,
* there is not enough changes left, so back track to the beginning and try the next edge available.
*/
if (kNumOfChanges >= 1) {
kNumOfChanges--;
listOfNodes.add(Snode.secondEndpoint()); //Adds the second end point to the array list.
Snode.secondEndpoint().setMark(true); //Marks the second end point as true, meaning it has been visited.
} else if(kNumOfChanges == 0 && graph.incidentEdges(endNode).hasNext()){ //If the number of changes available or remaining is 0:
break tryAgain2; //Try a different edge connecting to the endNode.
} else if(kNumOfChanges == 0 && !graph.incidentEdges(endNode).hasNext()) {
listOfNodes.remove(endNode); //So the node is removed.
endNode.setMark(false); //Marks the second end point to false, meaning it has not been visited.
break tryAgain; //Try a different incident edge.
}
} else {
listOfNodes.add(Snode.secondEndpoint()); //Adds the second end point to the array list.
Snode.secondEndpoint().setMark(true); //Marks the second end point as true, meaning it has been visited.
}
//If the second end point of the current node is the ending node, return the array list and end the program.
if (Snode.secondEndpoint().getName() == endLoc) {
return listOfNodes;
/*
* If it is not the ending node, check if all of its edges leads to an unmarked node (nodes that has not been visited).
* If there are no nodes that is unmarked (deadend), then this current node doesn't lead any where, so remove it from the
* array list.
*/
} else if (pathForEveryNode(allPathPossibilitiesOneNode(graph.incidentEdges(Snode.secondEndpoint()))) == null) {
listOfNodes.remove(Snode.secondEndpoint()); //remove the current node from the array list.
Snode.secondEndpoint().setMark(false); //Marks the current node to be false, meaning it has not been visited.
listOfNodes.remove(endNode); //So the node is removed.
endNode.setMark(false); //Marks the second end point to false, meaning it has not been visited.
if (kNumOfChanges > 1) {
kNumOfChanges++;
}
}
//Checks if the array list contains the ending node, if it does, then return the array list. Otherwise, return null.
boolean endLocInArray = false;
for(int i = 0; i < listOfNodes.size(); i++) {
if (listOfNodes.get(i).getName() == endLoc) {
endLocInArray = true;
break;
}
}
if(endLocInArray == true) {
return listOfNodes;
}
}}
}
}
return null;
}
and a helper method that checks if the second end point has already been visited or not:
private Iterator<GraphEdge> allPathPossibilitiesOneNode(Iterator<GraphEdge> PossibilitiesIterator) {
List<GraphEdge> allPathPossibilities = new ArrayList<GraphEdge>(); //Initializes the array list that will store the edges.
//This loop goes through all the incident edges connecting to the current node.
while (PossibilitiesIterator.hasNext()) {
GraphEdge currentEdge = PossibilitiesIterator.next(); //The first incident edge.
//This checks if the second end point (next intersection) is marked or not, if not, then add it to the array list.
if (currentEdge.secondEndpoint().getMark() == false) {
allPathPossibilities.add(currentEdge);
}
}
//Return the iterator is the array list is not empty, otherwise return null.
if (!allPathPossibilities.isEmpty()) {
return allPathPossibilities.iterator();
} else {
return null;
}
}
It's supposed to compare the busLine labels of the edge connected to the first node (firstEndPoint) to the edge connected to the secondEndPoint of the first edge to see if the bus routes are the same, if they are not the same then check whether there are enough bus changes left.
What I have so far does run without errors, but the solution printed out is already an empty list, even though it should not be.
We just started the topic on graphs, and is for an assignment.
Edit: example graph and solution:
The path for this map route is 0,1,5,6,10 for the nodes if 1 bus change is allowed.
java graph-traversal undirected-graph
asked Nov 28 '18 at 21:21
PengibabyPengibaby
946
I am currently doing a school assignment that wants us to model a bus route map using graphs (undirected), where the edges represent roads which has labels set to the bus route letter (one road may have have bus a, but another may have bus b) and the nodes represent intersections, dead end or the start and end locations. The map is in a rectangular/square grid format, so the maximum number of incident edges a node can have is 4 (meaning the intersection has 4 roads connected to it).
I have implemented the Node, Edge and Graph classes and also managed to add all the edges and nodes required to a graph that represent a sample map. I now have to write a method that uses a Iterator that stores the all the incident edges of a node and a integer value representing how many bus changes are allowed, and traverse through the graph to find ONE path that leads from the start node to the end node without using more bus changes than the specified. Then return a Iterator that stores all the nodes passed on the path from start to end.
This is what I have so far for the method (unfinished as I am stuck):
public Iterator<GraphNode> trip() throws GraphException {
GraphNode startNode = new GraphNode(startLoc); //Creates the starting node.
listOfNodes.add(startNode); //Adds the starting node to the list of nodes that will be the solution.
startNode.setMark(true); //Marks the starting node as true, meaning it has been visited.
pathForEveryNode(graph.incidentEdges(startNode)); //Uses the custom method to find where to go next.
return listOfNodes.iterator(); //Returns the iterator that stores the solution nodes.
}
private List<GraphNode> pathForEveryNode (Iterator<GraphEdge> incidentEdges) throws GraphException {
//This checks if the current node has incident edges or not, if not, then null is returned.
if (incidentEdges == null) {
return null;
} else {
//If the current node does have incident nodes, check the first edge first.
while (incidentEdges.hasNext()) {
tryAgain:{ GraphEdge nextEdge = incidentEdges.next(); //The is the first edge to be checked.
GraphNode endNode = nextEdge.secondEndpoint(); //This is the second end point of the current edge.
/*
* Checks if the current edge and one of the edges connected to the second end point has
* the same bus route set. If not, then the number of changes needs to be checked, if it is,
* then add the second end point to the array list and move to the next set of incident edges.
*/
listOfNodes.add(endNode); //Adds the second end point to the array list.
endNode.setMark(true); //Marks the second end point as true, meaning it has been visited.
tryAgain2:{GraphEdge Snode = graph.incidentEdges(endNode).next();
if (nextEdge.getBusLine() != Snode.getBusLine()) {
/*
* If the number of changes left is larger or equal to 1, it is decreased by 1. Otherwise,
* there is not enough changes left, so back track to the beginning and try the next edge available.
*/
if (kNumOfChanges >= 1) {
kNumOfChanges--;
listOfNodes.add(Snode.secondEndpoint()); //Adds the second end point to the array list.
Snode.secondEndpoint().setMark(true); //Marks the second end point as true, meaning it has been visited.
} else if(kNumOfChanges == 0 && graph.incidentEdges(endNode).hasNext()){ //If the number of changes available or remaining is 0:
break tryAgain2; //Try a different edge connecting to the endNode.
} else if(kNumOfChanges == 0 && !graph.incidentEdges(endNode).hasNext()) {
listOfNodes.remove(endNode); //So the node is removed.
endNode.setMark(false); //Marks the second end point to false, meaning it has not been visited.
break tryAgain; //Try a different incident edge.
}
} else {
listOfNodes.add(Snode.secondEndpoint()); //Adds the second end point to the array list.
Snode.secondEndpoint().setMark(true); //Marks the second end point as true, meaning it has been visited.
}
//If the second end point of the current node is the ending node, return the array list and end the program.
if (Snode.secondEndpoint().getName() == endLoc) {
return listOfNodes;
/*
* If it is not the ending node, check if all of its edges leads to an unmarked node (nodes that has not been visited).
* If there are no nodes that is unmarked (deadend), then this current node doesn't lead any where, so remove it from the
* array list.
*/
} else if (pathForEveryNode(allPathPossibilitiesOneNode(graph.incidentEdges(Snode.secondEndpoint()))) == null) {
listOfNodes.remove(Snode.secondEndpoint()); //remove the current node from the array list.
Snode.secondEndpoint().setMark(false); //Marks the current node to be false, meaning it has not been visited.
listOfNodes.remove(endNode); //So the node is removed.
endNode.setMark(false); //Marks the second end point to false, meaning it has not been visited.
if (kNumOfChanges > 1) {
kNumOfChanges++;
}
}
//Checks if the array list contains the ending node, if it does, then return the array list. Otherwise, return null.
boolean endLocInArray = false;
for(int i = 0; i < listOfNodes.size(); i++) {
if (listOfNodes.get(i).getName() == endLoc) {
endLocInArray = true;
break;
}
}
if(endLocInArray == true) {
return listOfNodes;
}
}}
}
}
return null;
}
and a helper method that checks if the second end point has already been visited or not:
private Iterator<GraphEdge> allPathPossibilitiesOneNode(Iterator<GraphEdge> PossibilitiesIterator) {
List<GraphEdge> allPathPossibilities = new ArrayList<GraphEdge>(); //Initializes the array list that will store the edges.
//This loop goes through all the incident edges connecting to the current node.
while (PossibilitiesIterator.hasNext()) {
GraphEdge currentEdge = PossibilitiesIterator.next(); //The first incident edge.
//This checks if the second end point (next intersection) is marked or not, if not, then add it to the array list.
if (currentEdge.secondEndpoint().getMark() == false) {
allPathPossibilities.add(currentEdge);
}
}
//Return the iterator is the array list is not empty, otherwise return null.
if (!allPathPossibilities.isEmpty()) {
return allPathPossibilities.iterator();
} else {
return null;
}
}
It's supposed to compare the busLine labels of the edge connected to the first node (firstEndPoint) to the edge connected to the secondEndPoint of the first edge to see if the bus routes are the same, if they are not the same then check whether there are enough bus changes left.
What I have so far does run without errors, but the solution printed out is already an empty list, even though it should not be.
We just started the topic on graphs, and is for an assignment.
Edit: example graph and solution:
The path for this map route is 0,1,5,6,10 for the nodes if 1 bus change is allowed.
java graph-traversal undirected-graph
java graph-traversal undirected-graph
asked Nov 28 '18 at 21:21
PengibabyPengibaby
946
asked Nov 28 '18 at 21:21
PengibabyPengibaby
946
edited Nov 29 '18 at 16:54
Pengibaby
asked Nov 28 '18 at 21:21
PengibabyPengibaby
946
asked Nov 28 '18 at 21:21
PengibabyPengibaby
946
asked Nov 28 '18 at 21:21
PengibabyPengibaby
946
946
Can you add an example graph and an example path through it? Will be very helpful
– mettleap
Nov 28 '18 at 21:28
Thank you for your reply! I have edited the original post with a image of a graph and the solution/path for that graph.
– Pengibaby
Nov 28 '18 at 21:32
read about Dijkstra's algorithm.
– user1373164
Nov 28 '18 at 21:34
Your question says the graphs are undirected and have no cycles, but your example has a cycle actually 2->3->7->6->2
– mettleap
Nov 28 '18 at 21:38
The solution we create cannot have cycles, which is the specification of the assignment. This graph was created using a file provided by the school.
– Pengibaby
Nov 28 '18 at 21:55
|
show 1 more comment
Can you add an example graph and an example path through it? Will be very helpful
– mettleap
Nov 28 '18 at 21:28
Thank you for your reply! I have edited the original post with a image of a graph and the solution/path for that graph.
– Pengibaby
Nov 28 '18 at 21:32
read about Dijkstra's algorithm.
– user1373164
Nov 28 '18 at 21:34
Your question says the graphs are undirected and have no cycles, but your example has a cycle actually 2->3->7->6->2
– mettleap
Nov 28 '18 at 21:38
The solution we create cannot have cycles, which is the specification of the assignment. This graph was created using a file provided by the school.
– Pengibaby
Nov 28 '18 at 21:55
Can you add an example graph and an example path through it? Will be very helpful
– mettleap
Nov 28 '18 at 21:28
Can you add an example graph and an example path through it? Will be very helpful
– mettleap
Nov 28 '18 at 21:28
Thank you for your reply! I have edited the original post with a image of a graph and the solution/path for that graph.
– Pengibaby
Nov 28 '18 at 21:32
Thank you for your reply! I have edited the original post with a image of a graph and the solution/path for that graph.
– Pengibaby
Nov 28 '18 at 21:32
read about Dijkstra's algorithm.
– user1373164
Nov 28 '18 at 21:34
read about Dijkstra's algorithm.
– user1373164
Nov 28 '18 at 21:34
Your question says the graphs are undirected and have no cycles, but your example has a cycle actually 2->3->7->6->2
– mettleap
Nov 28 '18 at 21:38
Your question says the graphs are undirected and have no cycles, but your example has a cycle actually 2->3->7->6->2
– mettleap
Nov 28 '18 at 21:38
The solution we create cannot have cycles, which is the specification of the assignment. This graph was created using a file provided by the school.
– Pengibaby
Nov 28 '18 at 21:55
The solution we create cannot have cycles, which is the specification of the assignment. This graph was created using a file provided by the school.
– Pengibaby
Nov 28 '18 at 21:55
|
show 1 more comment
0
active
oldest
votes
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53528292%2ffinding-a-path-from-start-to-end-by-traversing-a-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53528292%2ffinding-a-path-from-start-to-end-by-traversing-a-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Can you add an example graph and an example path through it? Will be very helpful
– mettleap
Nov 28 '18 at 21:28
Thank you for your reply! I have edited the original post with a image of a graph and the solution/path for that graph.
– Pengibaby
Nov 28 '18 at 21:32
read about Dijkstra's algorithm.
– user1373164
Nov 28 '18 at 21:34
Your question says the graphs are undirected and have no cycles, but your example has a cycle actually 2->3->7->6->2
– mettleap
Nov 28 '18 at 21:38
The solution we create cannot have cycles, which is the specification of the assignment. This graph was created using a file provided by the school.
– Pengibaby
Nov 28 '18 at 21:55