It's currently possible to create an undirected graph by adding edges from both u to v and v to u for all connected pairs (u, v). This requires a bit of extra space and more effort to set up.

The simplest solution I can think of is to add an undirected flag to Graph. When enabled, (v, u) would be added automatically when (u, v) is added. This would still require extra space but wouldn't require any other changes (e.g., to the shortest path algorithm).

hi , i want to install HTML server, but dont know how to install.
tried using command like this, we got error : WARNING: dijkstar 2.6.0 does not provide the extra 'server'

C:>pip install Dijkstar[server]
Requirement already satisfied: Dijkstar[server] in c:\program files\python\lib\site-packages (2.6.0)
WARNING: dijkstar 2.6.0 does not provide the extra 'server'
Requirement already satisfied: six in c:\program files\python\lib\site-packages (from Dijkstar[server]) (1.16.0)
C:>

thanks.

Hello,

I have created a simple graph by using a distance matrix.
Below you can find the code.

from dijkstar import Graph, find_path
matrix = ...... (distance matrix is created here)
graph = Graph()
for i in range(size):
    for j in range(size):
        graph.add_edge(i, j, {'cost': matrix[i][j]})        
cost_func = lambda u, v, e, prev_e: e['cost']
path = find_path(graph, 0, 6, cost_func=cost_func)
path

My question is, how am I able to learn the details of the founded path. There is a total cost, but I want to learn with which order of nodes I will get this cost. I want to learn the optimal order of nodes.

Thank you.

This fix is on the dev branch but hasn't been released

• Add example of simple, non-dynamic costs (i.e., no cost function)
• Modify the cost function example to show realistic usage of dynamic costs

Since dijkstar algorithm can get a node to another node's shortest path and the node to all other nodes' shortest path. But the project only shows the shortest path from node u to node v, the remaining information of the shortest paths from node u to all other nodes can not be retrieved, some usage of this remaining information can be used! Can you add the interface of getting node u to all other nodes' shortest paths? I'm looking for your rely!

Change predecessors[v] = (u, e, cost_of_e) to predecessors[v] = (u, e, cost_of_e, cost_of_s_to_u_plus_cost_of_e) in single_source_shortest_paths(), add a corresponding field to PathInfo, and update extract_shortest_path_from_predecessor_list().

I'm not sure off the top of my head what the use cases for this might be, but I saw that someone created a fork to replace cost_of_e with cost_of_s_to_u_plus_cost_of_e, so it's worth considering.

graph = Graph()
graph.add_edge(1, 2, {'cost': 10})
graph.add_edge(1, 5, {'cost': 1})
graph.add_edge(1, 6, {'cost': 100})
graph.add_edge(2, 3, {'cost': 1})
graph.add_edge(3, 4, {'cost': 1})
graph.add_edge(3, 5, {'cost': 1})
graph.add_edge(3, 6, {'cost': 100})
graph.add_edge(3, 7, {'cost': 1})
graph.add_edge(4, 3, {'cost': 1})
graph.add_edge(4, 7, {'cost': 1})
graph.add_edge(5, 1, {'cost': 1})
graph.add_edge(5, 3, {'cost': 1})
graph.add_edge(5, 7, {'cost': 1})
graph.add_edge(6, 1, {'cost': 100})
graph.add_edge(6, 3, {'cost': 100})
graph.add_edge(7, 5, {'cost': 1})
graph.add_edge(7, 3, {'cost': 1})
graph.add_edge(7, 4, {'cost': 1})

I run Dijkstra, find BEST path, then remove node from SPT and try to find the SPT without this node. Regarding my topology there is path between 1-5-7-3-4, but this module cannot find this

PathInfo(nodes=[1, 5, 3, 4], edges=[{'cost': 1}, {'cost': 1}, {'cost': 1}], costs=[1, 1, 1], total_cost=3)
took 5 from queue [5, 3]
pop {5} and became PathInfo(nodes=[1, 2, 3, 4], edges=[{'cost': 10}, {'cost': 1}, {'cost': 1}], costs=[10, 1, 1], total_cost=12)
took 3 from queue [5, 3, 2]
no backup path without {3, 5}

Hello. I've just started to use this library, but it seems that it is not creating shortest path well.
Let me show my example:
Im trying to get from top left corner to bottom right corner.
I create a graph 100 x 100 and then connecting nodes, which are red.
I use PIL to analyze image to get all pixels that are red (route)

This image works good
https://www.dropbox.com/s/vasji38qxvzvamo/test_route_good.jpg?dl=0

But this is not!
https://www.dropbox.com/s/bvmup96t1ckbeuh/test_route_bad.jpg?dl=0

Here is my source code:
https://www.dropbox.com/s/ezpzkklun7ut0kz/dijkstra_not_working.zip?dl=0

Here is corresponding Stackovewflow question
https://stackoverflow.com/questions/50307453/deijkstar-shortest-path-not-working

Hi,
does this support an undirected graph?

One use case for this would be to find nodes and edges with a given attribute value without having to iterate through all the nodes or edges. Possible API:

g = Graph()
g.add_edge(1, 2, tags={'type': 'highway'})
g.add_edge(2, 3, tags={'type': 'highway'})
highways = g.get_edges_by_tag(type='highway')

Internal tag storage might be a list:

def add_edge(self, u, v, edge=None, tags=None):
    ...
    if tags:
        self.tags.edges['type'].append(edge)

When there are multiple paths of the same length but one is cheaper than the other, the algorithm does not return the cheapest path.

Why is this? I have tried modifying the cost function from the example, but that has not seemed to work.

Thanks.