|
[x]
Posted via EE Mobile
|
||
Search, ask, and monitor your questions on the go with EE Mobile. Visit Experts Exchange from your mobile device and never be out of touch again. |
||
| Question |
|
[x]
Attachment Details
|
||
|
[x]
The Solution Rating System
|
||
With so many solutions, how can you tell which solutions are most likely to help you and which ones are not? To provide you with a tool to use, we rate our solutions based on various elements that most accurately determine if a solution is a quality solution. To explain what factors affect the solution rating, here are the elements we take into consideration when formulating our solution rating.
Your Input Matters If you have any suggestions that you would like to make for our rating system, please ask a question in the Suggestions Zone of Community Support. Thank you! |
||
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: |
//THE PART OF LINKED LIST:
public class List {
private static int MAX = Integer.MAX_VALUE;
private class Point {
int p, len;
Point next;
public Point(int x, int y){
p = x;
len = y;
next = null;
}
}
private Point head;
private Point tail;
public List(){
head = null;
tail = null;
}
//Add edge with vertex x and length len
public void add(int x, int len){
Point p = new Point(x, len);
if (head == null){
head = tail = p;
}
else{
tail.next = p;
tail = p;
}
}
//Get edge of vertex y
public int get(int y){
if (head == null)
return MAX;
Point id = head;
while (id != null){
if (id.p == y)
return id.len;
id = id.next;
}
return MAX;
}
//Remove the edge of vertex x
public int remove(int x){
if (head == null)
return MAX;
Point id = head;
if (head.p == x)
{
int val = head.len;
head = head.next;
return val;
}
while (id.next != null)
{
if (id.next.p == x)
{
int val = id.next.len;
id.next = id.next.next;
return val;
}
id = id.next;
}
return MAX;
}
}
//THE PART OF DIJSKTRA SHORTEST PATH ALGORITHM
// MAX = Integer.MAX_VALUE to denote infinity
//The List[] data = new List[n] stores the adjacency lists for n vertices
public static int shortestPath(List[] data, int n, int src, int dest){
Vector<Integer> t = new Vector<Integer>(); //Tenative set
int [] val = new int[n]; //Value of the shortest paths from src to other vertices
//Initial value for val[i] is the length between src and node i
for(int i = 0; i < n; i++){
val[i] = (i == src)? 0 : data[src].get(i);
}
//Add other vertices into tentative set
for (int i = 0; i < n; i++)
if (i != src)
t.add(i);
//As long as tentative set is not empty, we iterate
while (!t.isEmpty()){
int s = t.size(); //Size of tentative node
int min = 0;
//If there is no edge between permanent set and tentative set, we exit
for (int i = 1; i < s; i++){
int m = t.elementAt(i);
if (m!= src && val[t.elementAt(min)] > val[m])
min = i;
}
//Now we find the minimum path length
int k = t.elementAt(min); //Get the value of the node with minimum path length
//The smallest value is destination, so we remove it
if (k == dest)
return val[dest];
//If the minimum value is MAX, it means that there is no egdges left
if (val[k] == MAX)
return -1;
//Remove from tentative set
t.removeElementAt(min);
//Recalculate the value of the array val[]
for (int i = 0; i < n; i++)
if(i != src)
{
int tmp = MAX;
int u = data[k].get(i);
//There is an edge between i and k, calculate the length
if (u < MAX)
tmp = val[k] + u;
//Update val[i] if we have smaller path length
if (tmp < val[i])
val[i] = tmp;
}
}
//Return the value of the shortest path length from src to dest
return val[dest];
}
|
Advertisement
| Hall of Fame |