| 7 | |
| 8 | |
| 9 | std::vector<float> _dijkstra(Graph_L &G_l, int source, std::string weight, int target) { |
| 10 | const int dis_inf = 0x3f3f3f3f; |
| 11 | int N = G_l.n; |
| 12 | std::vector<float> dis(N+1,INFINITY); |
| 13 | Segment_tree_zkw segment_tree_zkw(N); |
| 14 | segment_tree_zkw.init(N); |
| 15 | segment_tree_zkw.change(source, 0); |
| 16 | dis[source] = 0; |
| 17 | std::vector<LinkEdge>& E = G_l.edges; |
| 18 | std::vector<int>& head = G_l.head; |
| 19 | while(segment_tree_zkw.t[1] != dis_inf) { |
| 20 | int u = segment_tree_zkw.num[1]; |
| 21 | if(u == 0) break; |
| 22 | segment_tree_zkw.change(u, dis_inf); |
| 23 | if(u == target){ |
| 24 | break; |
| 25 | } |
| 26 | for(register int p = head[u]; p != -1; p = E[p].next) { |
| 27 | int v = E[p].to; |
| 28 | if (dis[v] > dis[u] + E[p].w) { |
| 29 | dis[v] = dis[u] + E[p].w; |
| 30 | segment_tree_zkw.change(v, dis[v]); |
| 31 | } |
| 32 | } |
| 33 | } |
| 34 | |
| 35 | return dis; |
| 36 | |
| 37 | } |
| 38 | py::object _dijkstra_multisource(py::object G,py::object sources, py::object weight, py::object target) { |
| 39 | py::list res_lst = py::list(); |
| 40 | bool is_directed = G.attr("is_directed")().cast<bool>(); |
no test coverage detected