I implement the Dijkstra method in the "Additional Challenge" part of the main function, but I don't know how...
Even if I look at the implementation method, I don't understand the meaning from から...
import java.util.*;
public class Dijkstra {
public static void main(String[]args) {
final List <LocatedVertex>vertices=Arrays.asList(newLocatedVertex[]{
new LocatedVertex (0,40,150),
new LocatedVertex (1,110,80),
new LocatedVertex (2,110,150),
new LocatedVertex (3,110,220),
new LocatedVertex (4,190,80),
new LocatedVertex (5,190,150),
new LocatedVertex (6,190,220),
newLocatedVertex(7,260,150);
final List <WeightedEdge>edges=Arrays.asList (newWeightedEdge[]) {
new WeightedEdge (0,1,101,45),
new WeightedEdge(0,2,102,12),
new WeightedEdge (0,3,103,53),
new WeightedEdge (1, 2, 104, 7),
new WeightedEdge (1, 5, 105, 14),
new WeightedEdge(2,3,106,47),
new WeightedEdge(2,4,107,5),
new WeightedEdge(2,5,108,26),
new WeightedEdge(2,6,109,16),
new WeightedEdge (3, 5, 110, 8),
new WeightedEdge (4,1,111,9),
new WeightedEdge (4,7,112,23),
new WeightedEdge (5,4,113,2),
new WeightedEdge (5, 6, 114, 20),
new WeightedEdge (5, 7, 115, 11),
new WeightedEdge (6,3,116,18),
new WeightedEdge (6, 7, 117, 7);
final AdjacencyList aList = new AdjacencyList (8,edges);
GraphDrawDirectedGraph (vertices, aList, "Graph of interest");
List<WeightedEdge>spt=new ArrayList<WeightedEdge>();
// Additional challenges
/* 始 Determine the starting node
②Undefined (or infinite) points other than the starting node
③find the distance between all nodes adjacent to the starting node
④determine the shortest distance node
⑤Find the distance between all nodes adjacent to the established node
- The newly calculated distance is shorter than the current distance 新しく The newly calculated distance is defined as the fixed distance.
- Other than that 現在 Leave the current distance as the fixed distance
⑥Determine which node has the shortest distance among the nodes that have not been determined at this time
⑦Repeat operations ~ through を until all nodes are confirmed*/
List<LocatedVertex>s=vertices;//Initial value S=V
int[]d = new int[100]; // Minimum sum of perspective-to-vertex weights
int[]p = new int[s.size()]; // 1 previous vertex
while(!s.isEmpty()){
intu = 0;
}
GraphDrawDirectedGraph(vertices, spt, "shortest path tree");
}
}
import java.util.*;
/**
* adjacency list
*
*
*/
public classAdjacencyList{
private VertexAdjacencyList[] lists;// adjacency list
/**
* constructor for setting the number of vertices
*
* @paramn
* vertex number
*/
public AdjacencyList(intn){
lists = new VertexAdjacencyList[n];
for (inti=0; i<n;i++)
lists[i] = new VertexAdjacencyList();
}
/**
* CONSTRUCTOR FOR SETTING FROM NUMBER OF VERTICALS AND SIDE SET
*
* @paramn
* vertex number
* @paramedges
* List of side sets
*/
publicAdjacencyList(intn,List<WeightedEdge>edges){
This(n);
for (WeightedEdge:edges) {
lists [e.getHead()].add(new WeightedEdgeRecord(e.getToe(), e.getLabel(), e.getWeight()));
}
for(inti=0;i<n;i++){
Collections.sort(lists[i], new Comparator<WeightedEdgeRecord>(){
@ Override
public int compare (WeightedEdgeRecord r1, WeightedEdgeRecord r2) {
return r1.toe-r2.toe;
}
});
}
}
/**
* method of returning the number of vertices
*
* @return vertex number
*/
public int getNum(){
return lists.length;
}
/**
* Add side of weight to vertex toe to vertex number id
*
* @paramid
* vertex number
* @paramtoe
* the end of a side
* @param label
* label
* @param weight
* side weight
*/
public void addEdge(intid, inttoe, int label, int weight) {
lists [id].add (new WeightedEdgeRecord (toe, label, weight));
}
/**
* return the weight of a specified side
*
* @paramid1
* starting point
* @paramid2
* end point
* @return weight
*/
public WeightedEdge get WeightedEdge(intid1,intid2){
WeightedEdgee=null;
for (WeightedEdgeRecorder:lists [id1]) {
if(r.toe==id2){
e = new WeightedEdge (id1, id2, r.label, r.weight);
break;
}
}
return;
}
/**
* Returns a list of weighted directed sides originating from vertex number id
*
* @paramid
* vertex number
* @return List of weighted directed sides
*/
publicList<WeightedEdge>getWeightedEdges(intid){
List<WeightedEdge>ret=new ArrayList<>();
for (WeightedEdgeRecord:lists[id]){
ret.add(new WeightedEdge(id, record.toe, record.label, record.weight));
}
return;
}
public String to String() {
String ret = "adjacency list:\n";
for (inti=0;i<lists.length-1;i++)
ret+=String.format("%2d:%s\n", i,lists[i]);
ret+=String.format("%2d:%s\n", lists.length-1, lists[lists.length-1]);
return;
}
/**
* Adjacency list for one vertex
*/
private class VertexAdjacencyList extensions LinkedList <WeightedEdgeRecord > {
private static final long serialVersionUID = 1L;
public String to String() {
String ret="";
for (WeightedEdgeRecorder:this) {
ret+="->"+r;
}
return;
}
}
/**
* Adjacency List Records
*/
private class WeightedEdgeRecord {
private inttoe;// adjacency vertex
private int label;// label
private int weight;// weight
private WeightedEdgeRecord (intoe, int label, int weight) {
This.toe =toe;
This.label = label;
this.weight = weight;
}
public String to String() {
return String.format("[%d, %d]", toe, weight);
}
}
}
import java.awt.geom.Point2D;
/**
* coordinated vertex
*/
public classLocatedVertex{
/**
* vertex number
*/
private intid;
/**
* x-coordinate
*/
private int xPos = 0;
/**
* y-coordinate
*/
private intyPos = 0;
/**
* constructor giving only vertex numbers
* @paramid vertex number
*/
publicLocatedVertex(intid){
this.id=id;
}
/**
* constructor giving vertex numbers and coordinates
* @paramid vertex number
* @param xPos x coordinates
* @paramyPosy coordinates
*/
publicLocatedVertex(intid, intxPos, intyPos){
This(id);
this.xPos = xPos;
This.yPos =yPos;
}
public int getId(){
return id;
}
publicPoint2D.Double getPos(){
return new Point 2D.Double(xPos,yPos);
};
}
/**
* class representing the sides of a weighted graph
*
*/
public class WeightedEdge {
/**
* origin vertex in case of directed side
*/
private int head;
/**
* Ending vertex for directed side
*/
private inttoe;
/**
* Side Labels
*/
private int label;
/**
* side weight
*/
private int weight;
/**
* CONSTRUCTOR FOR GIVING ORIGINATION, END POINT, SIDE LABEL AND WEIGHT
* @param head Origin
* @paramote Ending point
* @param label side label
* @param weight weight
*/
public WeightedEdge(int head, inttoe, int label, int weight) {
This.head =head;
This.toe =toe;
This.label = label;
this.weight = weight;
}
public int getHead(){
return head;
}
public int getToe(){
return to;
}
public int getWeight() {
return weight;
}
/**
* Determine if the id of the starting point vertex is greater than the id of the ending point vertex.
* @return true/false
*/
public boolean isAnti() {
return head>toe;
}
public int getLabel(){
return label;
}
@ Override
public String to String() {
String ret;
if(weight!=0)
ret = String.format("%d", weight);
else
ret=";
return;
}
}
How about understanding it in the following order?
Let's forget about the program and understand what the Dijkstra method is doing by manually executing the Dijkstra method on a specific graph.It's a little troublesome, but please write down in your notebook how the condition changes with each step and understand the feeling of Dijkstra method.An example is a test of understanding.
Let's see how the program describes the Dijkstra method.What kind of data structure of Java is used to describe the graph, and what kind of code can you use to describe the steps from ~ to までの?
In this program, the graph is considered a set of vertices and a set of directed edges, and the set of vertices is expressed as a variable of type List<LocatedVertex> and a variable of type List<WeightedEdge>.For processing reasons, each vertex also has coordinate information, but the essential part of the Dijkstra method is the vertex number.For the sides, two vertex numbers specify the starting and ending points of the sides, and then specify the weight of the sides.
Next, we will start with か and think about how we can write it as a program.In 始Determining the starting node を, remember which of the vertex sets vertices.In the Dijkstra method, the starting point is determined from the beginning, so it's better to express the original input rather than the decision.This time, the vertex number is attached, so I will try to remember only the vertex number.Let's start with the vertex number 0.
intu=0
Let's try it here and make sure there are no errors.If not, move on.
Next, " 」Set points other than the starting node to undefined (or infinite)" is a bit difficult to understand, so if you chew it down, "Prepar a variable representing the shortest path distance from the starting point to the vertex, and initialize the non-start point to undefined (or infinite).Now, how do you implement it?It would be nice if there is a dictionary that shows the distance from the vertex number.If the vertex number always starts at zero and increases by one, you can use an array.
int[]d=new int[verts.size()]; //d[i] is the "distance to that vertex" to the vertex of the vertex number i.
int inf=(int)Double.POSITIVE_INFINITY;// Large integer value available
for (inti=1; i<d.length;i++) {
d[i] = inf; // Try initializing with a large integer value this time (you can treat it as "infinite" in integers)
}
Let's try it here and make sure there are no errors.If not, move on.
If you write from から to the end here, the answer will be too long, so let's stop here and continue to express the steps as source code to see if there are any errors.Particularly important is how to express "unconfirmed nodes."Pseudo-code found in Wikipedia and source code you can find if you search.
If you have any questions, try dividing them into small pieces and posting them as new questions.
Once you've implemented the Dijkstra method, test whether you've implemented what you think.Even if it is OK to check with one input example, the bug may be found in other input examples.Let's prepare a few input examples to see if they work well.
始Determine the starting node
At first, the starting point is determined by a hit.
始 Set points other than the starting node to undefined (or infinite)
Double.POSITIVE_INFINITY can be set to positive infinity.
始 Find the distance of all nodes adjacent to the starting node
If you read the source, it seems that AdjacencyList#getWeightedEdges(intid) can get a list of directed graphs that extend from the starting node. I think you can update the distance d[i] from this list.
最短 Determine the node with the shortest distance
Determine the smallest & least-selected node in the distance set d[i]. Specifically, the starting point distance d is 0, so it is the smallest in the distance set d[i], but it should not be determined as the shortest-distance node as the starting point should already be treated as selected.
確定 Find the distance between all nodes adjacent to the determined node
I think this can be solved by the same process as と.
現Currently, determine which nodes have the shortest distance among the nodes that have not been determined
I think this can be solved by the same process as と.
One thing I don't understand is int[]d=new int[100] and I think it's probably s.size(). (The minimum number of vertices to vertices is the number of vertices.)
List<LocatedVertex>s=vertices;//Initial value S=V
int[]d = new int[100]; // Minimum sum of perspective-to-vertex weights
int[]p = new int[s.size()]; // 1 previous vertex
while(!s.isEmpty()){
intu = 0;
}
© 2024 OneMinuteCode. All rights reserved.