Scientists create a computer memory out of cold atoms and light Computer Science |
- Scientists create a computer memory out of cold atoms and light
- Q Number Format: Who invented it? I can barely find any information about it let alone the actual inventors.
- Modification of Suurballe's algorithm (node disjoint paths)
- I want to create my own cryptocurrency
| Scientists create a computer memory out of cold atoms and light Posted: 01 Jul 2021 07:57 AM PDT |
| Posted: 01 Jul 2021 04:03 PM PDT |
| Modification of Suurballe's algorithm (node disjoint paths) Posted: 01 Jul 2021 07:06 AM PDT Hi, I will try the best to explain my problem. I have a graph/network which have nodes and edges obviously. Each edge have some cost, but they also have some kind of type. For simplicity let's just say it can be either a green or red edge. What I aim to achieve with all of this is to calculate two node disjoint paths with minimal cost, i.e. I need the two shortest/cost effective path where there are no overlapping nodes/vertices. With the graph described above I have been achieving this with success by implementing Suurballe's node-disjoint path algorithm (Disjoint Path Finding - Exterior Memory (macfreek.nl)). So that is working. However, what I did not mention in the beginning is that when going from one type of edge to another I would like some additional cost to be added. For now I have been achieving this by dividing nodes and edges into red and green nodes, with either a red or green edge between. Then when one node is actually used in both a green and red edge I split that node in two (a green and red node), where the edge between them adds the cost. And if I do some basic Dijkstra's algorithm on this, well, this works perfectly. But now comes the issue. When trying to combine these red/green split nodes AND Suurballe's algorithm, I run into a bit of a problem, which I haven't been able to solve. In the below figure I have tried to illustrate how Suurballe's algorithm works (not in as much detail as can be seen in the above link to how to actually implement it). So in the two top figures the first shortest path is found by Dijkstra's resulting in the path with the solid colored lines. The colors only indicate which type of edge this is (the ones that are black and have a small line below is just to indicate that that edge is not used, but is in fact either a red or green edge). The idea behind Suurballe's algorithm is that you split nodes in the first path into in and out nodes and alter the weight/cost of those edges, and direction, forcing certain ways when going onto certain branches. You then run Dijkstra's algorithm again on the modified graph, and the end result is the dashed path and essentially two paths (top left figure). If there are any overlapping edges between the two paths (in this case e-g), those edges are not used. Finally this result in two node disjoint paths, as illustrated in the top right figure. However, as I stated, this is without the node split and added cost of red and green edges. This situation I have tried to illustrate in the lower part of the figure. Here the weights of the edges have been changed compared to the top figures. But the same logic is applied. Here the "only" difference is that nodes that have both green and red edges going to/from them have been split into two nodes, and a new edge have been added between them which adds this additional cost. Otherwise nodes that only have green edges going to/from them are denoted with a _g (green), and edges with only red are denoted _r (red). And here comes the issue. As you can see in the path below Dijkstra's algorithm will first find the solid line path, which goes through e_g. Then by using SUurballe's algorithm it will find the dashed line in this case. BUT, this path goes through e_g, which technically belongs to the e_r node, i.e. it should not pick this path, or at least node, since it in theory should already be used. The correct paths are illustrated in the lower right figure instead. So, and I'm sorry for the long post, my final question is: How do I solve this ? [link] [comments]  |
| I want to create my own cryptocurrency Posted: 02 Jul 2021 03:27 AM PDT Hey guys,I am a 20 year old developer who is looking forward to creating his own crypto. I dont know much coding other than DSA and general coding. I dont know where to start and how much it will cost? Is it possible to create my own crypto for free? [link] [comments]  |
| You are subscribed to email updates from Computer Science: Theory and Application. To stop receiving these emails, you may unsubscribe now. | Email delivery powered by Google |
| Google, 1600 Amphitheatre Parkway, Mountain View, CA 94043, United States | |
No comments:
Post a Comment