algorithm - Will adding a single edge to a given graph create a new shortest path? -

-

assume have directed graph start node , end node c, , know shortest path c in graph of length n , uses nodes a, b0,b1, ..., bn-2, c.

i want know whether adding given new edge graph create new shortest path c of length < n. of course, use dijkstra's algorithm check shortest path in new graph, question whether information have shortest path in graph without new edge can somehow used solve problem more efficiently?

you add new edge (u,v), need check if triangular inequality holds:

d(v) < d(u) + w(u,v)

if does, there no new shortest path.

otherwise, have new shortest path source (a) v, invalidates shortest paths weight greater new d(v).


Comments

Post a Comment

Popular posts from this blog

Java 3D LWJGL collision -

-
i making 3d java game lwjgl library, , wondering how add collision detection, player not go through models. i using obj models. here objloader class, loads models: package renderengine; import java.io.bufferedreader; import java.io.file; import java.io.filenotfoundexception; import java.io.filereader; import java.util.arraylist; import java.util.list; import models.rawmodel; import org.lwjgl.util.vector.vector2f; import org.lwjgl.util.vector.vector3f; public class objloader { public static rawmodel loadobjmodel(string filename, loader loader){ filereader fr = null; try { fr = new filereader(new file("res/"+filename+".obj")); } catch (filenotfoundexception e) { system.err.println("couldn't load file!"); e.printstacktrace(); } bufferedreader reader = new bufferedreader(fr); string line; list<vector3f> vertices = new arraylist<vector3f...
Read more

spring - SubProtocolWebSocketHandler - No handlers -

-
i have ugly error during deploying spring app on jboss. 18:11:16,025 error [org.apache.catalina.core.containerbase.[jboss.web].[default-host].[/consumer]] (msc service thread 1-7) exception sending context initialized event listener instance of class org.springframework.web.context.contextloaderlistener: org.springframework.context.applicationcontextexception: failed start bean 'subprotocolwebsockethandler'; nested exception java.lang.illegalargumentexception: no handlers @ org.springframework.context.support.defaultlifecycleprocessor.dostart(defaultlifecycleprocessor.java:176) [spring-context-4.1.3.release.jar:4.1.3.release] @ org.springframework.context.support.defaultlifecycleprocessor.access$200(defaultlifecycleprocessor.java:51) [spring-context-4.1.3.release.jar:4.1.3.release] @ org.springframework.context.support.defaultlifecycleprocessor$lifecyclegroup.start(defaultlifecycleprocessor.java:346) [spring-context-4.1.3.release.jar:4.1.3.release] @ org.s...
Read more

methods - python can't use function in submodule -

-
my folder structure this: pythonstuff/ program.py modulea/ __init__.py foo.py bar.py here's code bar.py : def hello(): print("hello, world!") here's code program.py : #!/usr/bin/env python3 modulea import bar bar.hello() i run $ python3 program.py somehow error: file "program.py", line 3, in <module> bar.hello() attributeerror: 'module' object has no attribute 'hello' edit: __init__.py file empty. edit2: after trying realized had bar.py in root directory contained hello() method. bar.py in modulea/ directory empty. add it import os __all__ = [] module in os.listdir(os.path.dirname(__file__)): if module != '__init__.py' , module[-3:] == '.py': __all__.append(module[:-3]) the init .py files required make python treat directories containing packages; done prevent directories common name, such string, unintentionally hiding v...
Read more