我目前恢复旧的家庭作业,在那里我正在写一个程序,除其他功能,包括找图采用Dijkstra算法的最短路径。
我想我这样做是正确的大部分,但我不断收到 NullPointerException异常
在第58行执行时,如果(currentNode.getAktuell ())
。
我一直想几种解决方案来回,但似乎无法弄清楚什么是错误的,但 prioQueue.poll();
返回空
当队列为空。我试着来处理最后 currentNode
,最终变成零,但一直没能找到一个有效的解决方案,所以我开始觉得我已经错过了出来的东西在这里。
我真的AP preciate,如果有人熟悉dijkstras算法可以帮助我在这里。有大概的算法更好的解决方案,但我只想要帮助找出什么是错一个我写的,而不是用别人的算法答案。
公共静态列表<字符串> shortestPath(图<字符串>图中,字符串弗兰字符串到){
//如果(!pathExists(图,弗兰,直到))
//返回null;
的PriorityQueue< DjikstraObjekt<字符串>> prioQueue =新的PriorityQueue< DjikstraObjekt<字符串>>();
LinkedHashMap的<字符串,DjikstraObjekt<字符串>>三林=新的LinkedHashMap<字符串,DjikstraObjekt<字符串>>();
对于(字符串BLA:graph.getNodes())
samling.put(BLA,新DjikstraObjekt<字符串>(BLA,是Integer.MAX_VALUE,空,假));
samling.get(起价).updateVikt(0);
prioQueue.add(samling.get(起价));
而(!samling.get(至).getAktuell())
{
DjikstraObjekt<字符串> currentNode = prioQueue.poll();
如果(currentNode == NULL)
打破;
如果(currentNode.getAktuell())
继续;
currentNode.aktuellNod();
对于(ListEdge<字符串>边缘:graph.getEdgesFrom(currentNode.getNode()))
{
的System.out.println(得到的边缘);
INT nyVikt = edge.getVikt()+ currentNode.getVikt();
DjikstraObjekt<字符串> toNode = samling.get(edge.getDest());
如果(toNode.getAktuell()及!&安培; nyVikt&其中; toNode.getVikt()){
toNode.updateVikt(nyVikt);
toNode.setFrån(currentNode.getNode());
prioQueue.add(toNode);
}
}
}
名单<字符串> djikstaList =新的ArrayList<字符串>();
的for(int i = 0; I< samling.size();我++){
如果(samling.get(ⅰ).getNode()!=起价){
的System.out.println(samling.get(ⅰ).getNode());
djikstaList.add(samling.get(ⅰ).getNode());
}
}
返回djikstaList;
}
公共类DjikstraObjekt< E>实现可比< DjikstraObjekt< E>> {
私人电子邮件点头;
私人诠释vikt;
私人电子邮件frånNod;
私人布尔aktuellNod = FALSE;
公共DjikstraObjekt(E点头,诠释vikt,EfrånNod,布尔aktuellNod){
this.nod =点头;
this.vikt = vikt;
this.frånNod=frånNod;
this.aktuellNod = aktuellNod;
}
公共电子getNode(){
返回点头;
}
公共无效updateVikt(INT nyvikt){
vikt = nyvikt;
}
公众诠释getVikt(){
返回vikt;
}
公共布尔getAktuell(){
返回aktuellNod;
}
公共无效aktuellNod(){
aktuellNod = TRUE;
}
公共无效setFrån(E起价)
{
frånNod=起价;
}
公众诠释的compareTo(DjikstraObjekt< E>其他){
返回getVikt() - other.getVikt();
}
}
这是我的listEdge类:
公共类ListEdge< E> {
私人电子邮件DEST;
私人字符串NAMN;
私人整数vikt;
公共ListEdge(E DEST,字符串NAMN,整数vikt){
this.dest = DEST;
this.namn = NAMN;
this.vikt = vikt;
}
公共电子getDest(){
返回DEST;
}
公共无效ändraVikt(整数nyVikt){
如果(vikt℃,)
抛出新抛出:IllegalArgumentException();
vikt = nyVikt;
}
公共字符串getNamn(){
返回NAMN;
}
公众诠释的compareTo(ListEdge等){
返回this.vikt.compareTo(other.getVikt());
}
公众诠释getVikt(){
返回vikt;
}
公共字符串的toString(){
返回,直到+ DEST +配有+ NAMN ++ vikt;
}
}
这些应该是从我ListGraph类中的相应和方法:
公开名单< E> getNodes(){
名单< E>临时=新的ArrayList< E>();
对于(E测试:noder.keySet()){
temp.add(试验);
}
返回温度;
}
公开名单< ListEdge< E>> getEdgesFrom(E点头){
名单< ListEdge< E>>临时=新的ArrayList< ListEdge< E>>();
如果(noder.containsKey(点头)){
尝试{
对于(Map.Entry的< E,列表和LT; ListEdge< E>>>试验:noder.entrySet()){
如果(test.getKey()。等于(点头)){
的System.out.println(点头++ test.getKey());
对于(ListEdge< E> E:test.getValue()){
temp.add(E);
}
}
}
}
赶上(NoSuchElementException异常E){
}
}
返回温度;
}
解决方案
我不能重建,你向我们介绍了NullPointerException异常。由于莱昂德罗指出,该问题可能与躺着您的实现ListEdge和图的。
我做我自己这两个类的实现,以测试你的code。
唯一的问题,我能找到的是在创建结果列表的末尾:
的for(int i = 0; I< samling.size();我++){
如果(samling.get(ⅰ).getNode()!=起价){
这将始终在 NullPointerException异常
,因为的get()
需要一个键,你的情况结果,这是一个字符串
,而不是 INT
。遍历地图使用类似
名单,其中,字符串> djikstaList =新的ArrayList<字符串>();
对于(字符串键:samling.keySet()){
如果(samling.get(键).getNode()!=起价){
的System.out.println(samling.get(键).getNode());
djikstaList.add(samling.get(键).getNode());
}
}
此外,我想你wan't从返回从的实际路径
到
所以你需要以一个getter getFrån()
添加到 DijkstraObjekt
,然后建立这样的名单:
字符串FROMNODE = samling.get(到).getNode();
djikstaList.add(到);
而(FROMNODE!=从){
FROMNODE = samling.get(FROMNODE).getFrån();
djikstaList.add(FROMNODE);
}
在这个列表将包含完整路径(包括起始和结束点)以相反的顺序。
如果想要,我可以张贴我所有的课我用于测试/调试。
干杯 tannerli
I'm currently reviving an old homework assignment, where I'm writing a program that among other functions, involves finding the shortest path in a graph using Dijkstra's algorithm.
I think I've got it right for the most part, but I keep getting NullPointerException
at line 58 when executing if(currentNode.getAktuell())
.
I've been trying several solutions back and forth but can't seem to figure out what is wrong but prioQueue.poll();
returns null
when the queue is empty. I've tried to handle that last currentNode
that eventually turns into null but have not been able to find a working solution, so I'm starting to think that I've missed out on something here.
I would really appreciate it if someone familiar with dijkstras algorithm could help me out here. There's probably a better solution to the algorithm but I only want help with finding out what is wrong with the one I've written, and not "the answer" using someone else's algorithm.
public static List<String> shortestPath(Graph<String> graph, String från, String till){
//if(!pathExists(graph, från, till))
//return null;
PriorityQueue<DjikstraObjekt<String>> prioQueue = new PriorityQueue<DjikstraObjekt<String>>();
LinkedHashMap<String, DjikstraObjekt<String>> samling = new LinkedHashMap<String, DjikstraObjekt<String>>();
for(String bla : graph.getNodes())
samling.put(bla, new DjikstraObjekt<String>(bla, Integer.MAX_VALUE, null, false));
samling.get(från).updateVikt(0);
prioQueue.add(samling.get(från));
while(!samling.get(till).getAktuell())
{
DjikstraObjekt<String> currentNode = prioQueue.poll();
if(currentNode==null)
break;
if(currentNode.getAktuell())
continue;
currentNode.aktuellNod();
for(ListEdge<String> edge : graph.getEdgesFrom(currentNode.getNode()))
{
System.out.println("get edges from");
int nyVikt = edge.getVikt() + currentNode.getVikt();
DjikstraObjekt<String> toNode = samling.get(edge.getDest());
if(!toNode.getAktuell() && nyVikt < toNode.getVikt()) {
toNode.updateVikt(nyVikt);
toNode.setFrån(currentNode.getNode());
prioQueue.add(toNode);
}
}
}
List<String> djikstaList = new ArrayList<String>();
for(int i=0;i<samling.size();i++){
if(samling.get(i).getNode()!=från){
System.out.println(samling.get(i).getNode());
djikstaList.add(samling.get(i).getNode());
}
}
return djikstaList;
}
public class DjikstraObjekt<E> implements Comparable<DjikstraObjekt<E>> {
private E nod;
private int vikt;
private E frånNod;
private boolean aktuellNod=false;
public DjikstraObjekt(E nod, int vikt, E frånNod, boolean aktuellNod){
this.nod=nod;
this.vikt=vikt;
this.frånNod=frånNod;
this.aktuellNod=aktuellNod;
}
public E getNode() {
return nod;
}
public void updateVikt(int nyvikt){
vikt=nyvikt;
}
public int getVikt() {
return vikt;
}
public boolean getAktuell() {
return aktuellNod;
}
public void aktuellNod(){
aktuellNod=true;
}
public void setFrån(E från)
{
frånNod = från;
}
public int compareTo(DjikstraObjekt<E> other) {
return getVikt() - other.getVikt();
}
}
Heres my listEdge class:
public class ListEdge<E> {
private E dest;
private String namn;
private Integer vikt;
public ListEdge(E dest, String namn, Integer vikt){
this.dest=dest;
this.namn=namn;
this.vikt=vikt;
}
public E getDest(){
return dest;
}
public void ändraVikt(Integer nyVikt){
if(vikt<0)
throw new IllegalArgumentException();
vikt=nyVikt;
}
public String getNamn(){
return namn;
}
public int compareTo(ListEdge other) {
return this.vikt.compareTo(other.getVikt());
}
public int getVikt(){
return vikt;
}
public String toString(){
return "till " + dest + " med " + namn +" "+ vikt;
}
}
These should be the relevent methods from my ListGraph class:
public List<E> getNodes(){
List<E> temp = new ArrayList<E>();
for(E test : noder.keySet()){
temp.add(test);
}
return temp;
}
public List<ListEdge<E>> getEdgesFrom(E nod) {
List<ListEdge<E>> temp = new ArrayList<ListEdge<E>>();
if(noder.containsKey(nod)){
try{
for(Map.Entry<E, List<ListEdge<E>>> test : noder.entrySet()){
if(test.getKey().equals(nod)){
System.out.println(nod+" "+test.getKey());
for(ListEdge<E> e: test.getValue()){
temp.add(e);
}
}
}
}
catch(NoSuchElementException E){
}
}
return temp;
}
解决方案
I couldn't reconstruct the NullPointerException you told us about. As Leandro pointed out, the problem might lay with your implementation of ListEdge and Graph.
I did an implementation of both classes myself to test your code.
The only problem I could find was in the end where you create the result list:
for(int i=0;i<samling.size();i++){
if(samling.get(i).getNode()!=från){
This will always Result in a NullPointerException
because get()
expects a key and in your case that's a String
, not an int
. To iterate over the Map use something like
List<String> djikstaList = new ArrayList<String>();
for(String key : samling.keySet()){
if(samling.get(key).getNode()!=från){
System.out.println(samling.get(key).getNode());
djikstaList.add(samling.get(key).getNode());
}
}
Furthermore, i assume you wan't to return the actual path from from
to to
so you would need to add a getter getFrån()
to DijkstraObjekt
and then build up the list like this:
String fromNode = samling.get(to).getNode();
djikstaList.add(to);
while(fromNode != from){
fromNode = samling.get(fromNode).getFrån();
djikstaList.add(fromNode);
}
After this the List will contain the complete path (including Start and End node) in reverse order.
If wanted, I can post all of my classes I used for testing/debugging.
Cheers tannerli