在非加权无向图中去除最小边缘以强制增加最短路径长度的算法
Ali*_*ani 8 algorithm graph-theory shortest-path graph-algorithm
给定未加权无向图的邻接矩阵,是否有一种有效的方法(多项式算法)来扩展/增加任何给定的两个节点s和t之间的最短路径的长度？
例:
在下面的例子中,从顶点s = 1到顶点t = 5有5个不同的"最短路径",每个都有3个长度.我想删除最少数量的边缘,以便最短路径长度被强制为4或更多.(断开图表是可以的.)
邻接矩阵(扩展以纠正示例):
0 1 0 0 0 1 1 1 0 1 0
1 0 1 1 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 0 0 1
0 1 0 0 1 1 0 0 0 0 0
0 0 1 1 0 1 0 0 0 0 0
1 0 0 1 1 0 0 0 1 0 0
1 0 0 0 0 0 0 0 1 0 0
1 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 1 1 1 0 0 0
1 0 0 0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0 0 1 0
代表这个图:
迫使最短路径长度从3增加到4的最小成本是删除两条边(1,2)和(5,9)
目标:
你能否提出一个通用算法的想法,找到一般情况下必须删除的边集？
更正:如我的评论中所述,此示例不完整.通过添加另外两个顶点10和11(以红色显示),该示例被挽救.
我用“P\xc3\xa5l GD”答案的第三条评论中提到的方法解决了这个问题。这是它的 java 代码。希望您觉得它有帮助！
\n\n// BFS to find the depth of every node (from source node)\n// graph is the adjacency matrix.\n// elements of row zero and column zero are all useless. this program\n// works with indices >=1 \nprivate int[][] BFS (int[][] graph, int source, boolean SPedges){\n int[][] temp = null;\n\n // nodes is number of graph nodes. (nodes == graph.length - 1)\n if (SPedges){\n temp = new int[nodes + 1][nodes + 1];\n }\n else{\n depth[source] = 0;\n }\n LinkedList<Integer> Q = new LinkedList<Integer>();\n Q.clear();\n visited[source] = true;\n Q.addFirst(source);\n while (!Q.isEmpty()){\n int u = Q.removeLast();\n for (int k = 1; k <= nodes; k++){\n if (!SPedges){\n // checking if there\'s a edge between node u and other nodes\n if (graph[u][k] == 1 && visited[k] == false){\n visited[k] = true;\n depth[k] = depth[u] + 1;\n Q.addFirst(k);\n }\n }\n else{\n if (graph[u][k] == 1 && depth[k] == depth[u] - 1){\n Q.addFirst(k);\n temp[k][u] = 1;\n }\n }\n } \n }\n return temp;\n}\n\n// fills the edges of shortest path graph in flow \nprivate ArrayList<Edge> maxFlow(int[][] spg, int source, int sink){ \n int u = source;\n ArrayList<Integer> path = new ArrayList<Integer> (depth[sink]);\n path.add(source);\n Arrays.fill(visited, false);\n visited[source] = true;\n for (int i = 1; i <= nodes + 1; i++){\n if (i == nodes + 1){\n if (u == source)\n break;\n u = path.get(path.size() - 2);\n i = path.remove(path.size() - 1);\n }\n else if(spg[u][i] == 1 && visited[i] == false){\n visited[i] = true;\n path.add(i);\n if (i == sink){\n for(int k = 0; k < path.size() - 1; k++){\n spg[path.get(k)][path.get(k+1)] = 0;\n spg[path.get(k+1)][path.get(k)] = 1;\n }\n i = 0;\n u = source;\n path.clear();\n path.add(u);\n Arrays.fill(visited, false);\n }\n else{\n u = i;\n i = 0;\n }\n }\n }\n\n LinkedList<Integer> Q = new LinkedList<Integer>();\n Q.clear();\n\n Arrays.fill(visited, false);\n\n visited[source] = true;\n Q.addFirst(source);\n while (!Q.isEmpty()){\n u = Q.removeLast();\n for (int k = 1; k <= nodes; k++){\n if (spg[u][k] == 1 && visited[k] == false){\n visited[k] = true;\n Q.addFirst(k);\n } \n }\n }\n ArrayList<Edge> edges = new ArrayList<Edge>();\n for (int i = 1; i <= nodes; i++){\n for (int j = 1; j <= nodes; j++){\n if ((spg[i][j] == 1) && (visited[i] ^ visited[j])){\n edges.add(new Edge(i, j));\n }\n }\n }\n\n return edges;\n}\n\npublic void Solv(){\n // adjacency matrix as g. represents the graph.\n // first we find depth of each node corresponding to source node by a BFS from source\n BFS(g, s, false);\n\n // shortest path length from source to sink (node t)\n SPL = depth[t];\n\n // shortest path graph\n // it\'s a subgraph of main graph consisting only edges that are in a shortest path\n // between s and t\n spg = BFS(g, t, true);\n\n // lastly we find edges of a min cut in shortest paths graph\n // and store them in "edges"\n edges = maxFlow(spg, s, t);\n} \n\nclass Edge{\n private int begin, end;\n public Edge(int begin, int end){\n this.begin = begin;\n this.end = end;\n }\n @Override\n public String toString() {\n return new String(String.valueOf(begin) + " " + String.valueOf(end));\n }\n}\n