Untitled

daskalot

May 14th, 2019

278

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

text 4.62 KB | None | 0 0

raw download clone embed print report

package aps2.shortestpath;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Vector;
class Edge{
String from;
String to;
int weight;
Edge(String f,String s,int w){
from = f;
to = s;
weight = w;
}
}
public class ShortestPath {
boolean negCycle;
Vector<Edge> adj;
Map<String,Integer> idxEdges;
Map<String,Integer> idx;
int shortestDistances[];
String parent[];
int totalNodes, totalEdges;
int INF;
Vector<String> vecNodes;
ShortestPath(){
this.totalNodes = 0;
this.totalEdges = 0;
this.adj = new Vector<Edge>();
this.idxEdges = new HashMap<String,Integer>();
this.idx = new HashMap<String,Integer>();
this.vecNodes = new Vector<String>();
this.INF = Integer.MAX_VALUE;
}
/**
* In this task you need to find a shortest path on a given directed graph
* with arbitrary edge lengths (including negative weights!) from a single
* source node to all other nodes in the graph.
*
* Your algorithm should also detect, if there is a negative cycle in the
* graph and return null in this case.
*/
/**
* Adds a new node named s to the graph.
*
* @param s Name of the node
* @return True, if a node is unique and successfully added; False otherwise.
*/
public boolean addNode(String s) {
if(vecNodes.contains(s)) return false;
idx.put(s,totalNodes);
vecNodes.add(s);
totalNodes++;
return true;
}
/**
* Returns names of all nodes in the graph.
*
* @return Names of all nodes in the graph.
*/
public Vector<String> getNodes() {
return vecNodes;
}
/**
* Adds an edge from node a to node b.
*
* @param a Source node.
* @param b Target node.
* @param w Edge weight. Warning: The weight can also be negative!
*/
public void addEdge(String a, String b, int w) {
if(idxEdges.containsKey(a+b)) {
int i = idxEdges.get(a+b);
adj.set(i,new Edge(a,b,w));
}
else {
adj.add(new Edge(a,b,w));
idxEdges.put(a+b,totalEdges);
totalEdges++;
}
}
/**
* Computes and locally stores shortest paths from the given origin node
* to all other nodes in the graph.
*
* @param start Origin node.
*/
public void computeShortestPaths(String start) {
negCycle = false;
shortestDistances = new int[totalNodes+1];
parent = new String[totalNodes+1];
for(int i=0;i<totalNodes+1;i++) shortestDistances[i] = INF;
for(int i=0;i<totalNodes+1;i++) parent[i] = null;
shortestDistances[idx.get(start)]=0;
parent[idx.get(start)] = start;
for(int i=1;i<totalNodes;i++) {
for(int j=0;j<totalEdges;j++) {
Edge e = adj.elementAt(j);
int from = idx.get(e.from), to = idx.get(e.to);
if(shortestDistances[from]!=INF && shortestDistances[from]+e.weight<shortestDistances[to])
shortestDistances[to] = shortestDistances[from] + e.weight;
parent[to] = e.from;
}
}
for(int i=0;i<totalEdges;i++) {
Edge e = adj.elementAt(i);
int from = idx.get(e.from);
int to = idx.get(e.to);
if(shortestDistances[from]!=INF && shortestDistances[from] + e.weight < shortestDistances[to]) {
negCycle = true;
return;
}
}
}
/**
* Returns a list of nodes on the shortest path from the given origin to
* destination node. Returns null, if a path does not exist or there is a
* negative cycle in the graph.
*
* @param start Origin node
* @param dest Destination node
* @return List of nodes on the shortest path from start to dest or null, if the nodes are not connected or there is a negative cycle in the graph.
*/
public Vector<String> getShortestPath(String start, String dest) {
computeShortestPaths(start);
System.out.println(idx.get(start)+" "+idx.get(dest));
if(negCycle || shortestDistances[idx.get(dest)] == INF) return null;
Vector<String> res = new Vector<String>();
for(int i=0;i<totalNodes;i++) {
System.out.print(i+":"+idx.get(parent[i])+" ");
}
String current = start;
return null;
}
/**
* Returns the distance of the shortest path from the given origin to
* destination node. Returns Integer.MIN_VALUE, if a path does not exist
* or there is a negative cycle in the graph.
*
* @param start Origin node
* @param dest Destination nodes
* @return Distance of the shortest path from start to dest or Integer.MIN_VALUE, if the nodes are not connected or there is a negative cycle in the graph.
*/
public int getShortestDist(String start, String dest) {
computeShortestPaths(start);
if(negCycle || shortestDistances[idx.get(dest)] == INF) return Integer.MIN_VALUE;
return shortestDistances[idx.get(dest)];
}
}

Add Comment

Please, Sign In to add comment