Dado un gráfico bidireccional no ponderado que contiene N Nodes y M aristas representados por una array arr[][2] . La tarea es encontrar la diferencia en la longitud de las rutas más cortas y la segunda más corta desde el Node 1 hasta N . Si la segunda ruta más corta no existe, imprima 0 .
Nota: El gráfico está conectado, no contiene múltiples aristas ni bucles propios. (2<=N<=20)
Ejemplos:
Entrada: N = 4, M = 4, arr[M][2]={{1, 2}, {2, 3}, {3, 4}, {1, 4}}
Salida: 2
Explicación: El más corto la ruta es 1->4 y la segunda ruta más corta es 1->2->3->4. Por lo tanto, la diferencia es 2.Entrada: N = 6, M = 8, array[M][2]={{1, 2}, {1, 3}, {2, 6}, {2, 3}, {2, 4}, { 3, 4}, {3, 5}, {4, 6}}
Salida: 1
Enfoque: la idea es realizar la primera búsqueda en profundidad para encontrar todas las rutas posibles y almacenarlas en un vector , ordenar el vector y encontrar la diferencia entre la ruta más corta y la segunda más corta. Siga los pasos a continuación para resolver el problema:
- Defina una función dfs(vector<vector<int> >& graph, int s, int e, vector<int> vis, int count, vector<int>& dp) y realice los siguientes pasos:
- Si s es igual a e , entonces significa que la ruta actual es una de las posibles, empuje el valor de count en el vector dp[] y regrese.
- Itere sobre el rango [0, graph[s]] usando la variable i y realizando los siguientes pasos:
- Si vis[i] no es igual a 1, establezca el valor de vis[i] en 1 y llame a la función dfs(graph, i, e, vis, count+1, dp) para encontrar otras rutas posibles y establezca el valor de vis[0] de nuevo a 0.
- Inicialice un gráfico vectorial 2-D [][] con N número de filas para almacenar los vértices conectados desde cada vértice.
- Iterar sobre el rango [0, M] usando la variable i y realizar los siguientes pasos:
- Introduzca el valor de b-1 en el gráfico vectorial [][] en la fila a-1.
- Introduzca el valor de a-1 en el gráfico vectorial [][] en la fila b-1.
- Inicialice un vector vis[] de tamaño N para realizar un seguimiento de los Nodes visitados.
- Inicialice un vector dp[] para almacenar la longitud de todas las rutas posibles.
- Llame a la función dfs(graph, 0, N-1, vis, 0, dp) para encontrar todas las rutas posibles y almacenarlas en el vector dp[] .
- Ordene el vector dp[] en orden ascendente.
- Si el tamaño del vector dp[] es mayor que 1, devuelva el valor dp[1]-dp[0]; de lo contrario, devuelva 0 como respuesta.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// DFS function to find all possible paths.
void dfs(vector<vector<int> >& graph, int s, int e,
vector<int> v, int count, vector<int>& dp)
{
if (s == e) {
// Push the number of nodes required for
// one of the possible paths
dp.push_back(count);
return;
}
for (auto i : graph[s]) {
if (v[i] != 1) {
// Mark the node as visited and
// call the function to search for
// possible paths and unmark the node.
v[i] = 1;
dfs(graph, i, e, v, count + 1, dp);
v[i] = 0;
}
}
}
// Function to find the difference between the
// shortest and second shortest path
void findDifference(int n, int m, int arr[][2])
{
// Construct the graph
vector<vector<int> > graph(n, vector<int>());
for (int i = 0; i < m; i++) {
int a, b;
a = arr[i][0];
b = arr[i][1];
graph[a - 1].push_back(b - 1);
graph[b - 1].push_back(a - 1);
}
// Vector to mark the nodes as visited or not.
vector<int> v(n, 0);
// Vector to store the count of all possible paths.
vector<int> dp;
// Mark the starting node as visited.
v[0] = 1;
// Function to find all possible paths.
dfs(graph, 0, n - 1, v, 0, dp);
// Sort the vector
sort(dp.begin(), dp.end());
// Print the difference
if (dp.size() != 1)
cout << dp[1] - dp[0];
else
cout << 0;
}
// Driver Code
int main()
{
int n, m;
n = 6;
m = 8;
int arr[m][2]
= { { 1, 2 }, { 1, 3 },
{ 2, 6 }, { 2, 3 },
{ 2, 4 }, { 3, 4 },
{ 3, 5 }, { 4, 6 } };
findDifference(n, m, arr);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class Main
{
// DFS function to find all possible paths.
static void dfs(Vector<Vector<Integer>> graph, int s,
int e, int[] v, int count, Vector<Integer> dp) {
if (s == e)
{
// Push the number of nodes required for
// one of the possible paths
dp.add(count);
return;
}
for(int i : graph.get(s)) {
if (v[i] != 1)
{
// Mark the node as visited and
// call the function to search for
// possible paths and unmark the node.
v[i] = 1;
dfs(graph, i, e, v, count + 1, dp);
v[i] = 0;
}
}
}
// Function to find the difference between the
// shortest and second shortest path
static void findDifference(int n, int m, int[][] arr)
{
// Construct the graph
Vector<Vector<Integer>> graph = new Vector<Vector<Integer>>();
for(int i = 0; i < n; i++)
{
graph.add(new Vector<Integer>());
}
for (int i = 0; i < m; i++) {
int a, b;
a = arr[i][0];
b = arr[i][1];
graph.get(a - 1).add(b - 1);
graph.get(b - 1).add(a - 1);
}
// Vector to mark the nodes as visited or not.
int[] v = new int[n];
Arrays.fill(v, 0);
// Vector to store the count of all possible paths.
Vector<Integer> dp = new Vector<Integer>();
// Mark the starting node as visited.
v[0] = 1;
// Function to find all possible paths.
dfs(graph, 0, n - 1, v, 0, dp);
// Sort the vector
Collections.sort(dp);
// Print the difference
if (dp.size() != 1) System.out.print(dp.get(1) - dp.get(0));
else System.out.print(0);
}
public static void main(String[] args) {
int n, m;
n = 6;
m = 8;
int[][] arr
= { { 1, 2 }, { 1, 3 },
{ 2, 6 }, { 2, 3 },
{ 2, 4 }, { 3, 4 },
{ 3, 5 }, { 4, 6 } };
findDifference(n, m, arr);
}
}
// This code is contributed by mukesh07.
Python3
# Python3 program for the above approach # DFS function to find all possible paths. def dfs(graph, s, e, v, count, dp): if (s == e): # Push the number of nodes required for # one of the possible paths dp.append(count) return for i in graph[s]: if (v[i] != 1): # Mark the node as visited and # call the function to search for # possible paths and unmark the node. v[i] = 1 dfs(graph, i, e, v, count + 1, dp) v[i] = 0 # Function to find the difference between the # shortest and second shortest path def findDifference(n, m, arr): # Construct the graph graph = [] for i in range(n): graph.append([]) for i in range(m): a = arr[i][0] b = arr[i][1] graph[a - 1].append(b - 1) graph[b - 1].append(a - 1) # Vector to mark the nodes as visited or not. v = [0]*(n) # Vector to store the count of all possible paths. dp = [] # Mark the starting node as visited. v[0] = 1 # Function to find all possible paths. dfs(graph, 0, n - 1, v, 0, dp) # Sort the vector dp.sort() # Print the difference if (len(dp) != 1): print(dp[1] - dp[0], end = "") else: print(0, end = "") # Driver Code n = 6 m = 8 arr = [ [1, 2], [1, 3], [2, 6], [2, 3], [2, 4], [3, 4], [3, 5], [4, 6], ] findDifference(n, m, arr) # This code is contributed by divyesh072019.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// DFS function to find all possible paths.
static void dfs(List<List<int>> graph, int s, int e, List<int> v, int count, List<int> dp) {
if (s == e)
{
// Push the number of nodes required for
// one of the possible paths
dp.Add(count);
return;
}
foreach(int i in graph[s]) {
if (v[i] != 1)
{
// Mark the node as visited and
// call the function to search for
// possible paths and unmark the node.
v[i] = 1;
dfs(graph, i, e, v, count + 1, dp);
v[i] = 0;
}
}
}
// Function to find the difference between the
// shortest and second shortest path
static void findDifference(int n, int m, int[,] arr)
{
// Construct the graph
List<List<int>> graph = new List<List<int>>();
for(int i = 0; i < n; i++)
{
graph.Add(new List<int>());
}
for (int i = 0; i < m; i++) {
int a, b;
a = arr[i,0];
b = arr[i,1];
graph[a - 1].Add(b - 1);
graph[b - 1].Add(a - 1);
}
// Vector to mark the nodes as visited or not.
List<int> v = new List<int>();
for(int i = 0; i < n; i++)
{
v.Add(0);
}
// Vector to store the count of all possible paths.
List<int> dp = new List<int>();
// Mark the starting node as visited.
v[0] = 1;
// Function to find all possible paths.
dfs(graph, 0, n - 1, v, 0, dp);
// Sort the vector
dp.Sort();
// Print the difference
if (dp.Count != 1) Console.Write(dp[1] - dp[0]);
else Console.Write(0);
}
static void Main() {
int n, m;
n = 6;
m = 8;
int[,] arr
= { { 1, 2 }, { 1, 3 },
{ 2, 6 }, { 2, 3 },
{ 2, 4 }, { 3, 4 },
{ 3, 5 }, { 4, 6 } };
findDifference(n, m, arr);
}
}
// This code is contributed by decode2207.
Javascript
<script>
// Javascript program for the above approach
// DFS function to find all possible paths.
function dfs(graph, s, e, v, count, dp) {
if (s == e)
{
// Push the number of nodes required for
// one of the possible paths
dp.push(count);
return;
}
for (let i of graph[s]) {
if (v[i] != 1)
{
// Mark the node as visited and
// call the function to search for
// possible paths and unmark the node.
v[i] = 1;
dfs(graph, i, e, v, count + 1, dp);
v[i] = 0;
}
}
}
// Function to find the difference between the
// shortest and second shortest path
function findDifference(n, m, arr)
{
// Construct the graph
let graph = new Array(n).fill(0).map(() => []);
for (let i = 0; i < m; i++) {
let a, b;
a = arr[i][0];
b = arr[i][1];
graph[a - 1].push(b - 1);
graph[b - 1].push(a - 1);
}
// Vector to mark the nodes as visited or not.
let v = new Array(n).fill(0);
// Vector to store the count of all possible paths.
let dp = [];
// Mark the starting node as visited.
v[0] = 1;
// Function to find all possible paths.
dfs(graph, 0, n - 1, v, 0, dp);
// Sort the vector
dp.sort((a, b) => a - b);
// Print the difference
if (dp.length != 1) document.write(dp[1] - dp[0]);
else document.write(0);
}
// Driver Code
let n, m;
n = 6;
m = 8;
let arr = [
[1, 2],
[1, 3],
[2, 6],
[2, 3],
[2, 4],
[3, 4],
[3, 5],
[4, 6],
];
findDifference(n, m, arr);
// This code is contributed by gfgking.
</script>
Producción
1
Complejidad de tiempo: O(2^N)
Espacio auxiliar: O(N)
Enfoque eficiente: utilizando el hecho de que el segundo camino más corto no puede contener todos los bordes iguales que en el camino más corto. Elimine cada borde del camino más corto uno a la vez y siga encontrando el camino más corto, luego uno de ellos tiene que ser el segundo camino más corto requerido. Utilice Breadth First Search para encontrar la solución de manera óptima. Siga los pasos a continuación para resolver el problema:
- Defina una función get_edges(int s, vector<int>& edge, vector<int> p) y realice los siguientes pasos:
- Si s es igual a -1, entonces regresa.
- Llame a la función get_edges(p[s], edges, p) para encontrar todos los bordes a lo largo del camino más corto.
- Introduzca el valor de s en los bordes del vector [].
- Defina una función dist_helper(vector<vector<int> > graph, vector<int>& d, int v1, int v2, int N) y realice los siguientes pasos:
- Inicialice el vector vis[] para realizar un seguimiento de los Nodes visitados.
- Inicialice una cola de pares q[] para realizar la búsqueda primero en anchura y encontrar la ruta.
- Ponga en cola el par {0, 0} en la cola de pares q[].
- Marque el valor de vis[0] como 1(visitado) .
- Iterar en un bucle while hasta que la cola de pares q[] no esté vacía.
- Inicialice una variable a como el frente de la cola de pares q[] y elimine un elemento de la cola de pares q[].
- Itere sobre el rango [0, graph[a.first]] usando la variable i y realizando los siguientes pasos:
- Si i es igual a v1 y a.first es igual a v2 o i es igual a v2 y a.first es igual a v1, entonces continúe .
- Si vis[i] es igual a 0, establezca el valor de d[i] como 1+a.segundo, p[i] como a.primero y vis[i] como 1 y ponga en cola el par {i, d[ i]} en la cola de pares q[].
- Defina una función dist(vector<vector<int> > graph, vector<int>& d, vector<int> &p, int N) y realice los siguientes pasos:
- Inicialice el vector vis[] para realizar un seguimiento de los Nodes visitados.
- Inicialice una cola de pares q[] para realizar la búsqueda primero en anchura y encontrar la ruta.
- Ponga en cola el par {0, 0} en la cola de pares q[].
- Marque el valor de vis[0] como 1(visitado) .
- Iterar en un bucle while hasta que la cola de pares q[] no esté vacía.
- Inicialice la variable a como el frente de la cola de pares q[] y elimine un elemento de la cola de pares q[].
- Itere sobre el rango [0, graph[a.first]] usando la variable i y realizando los siguientes pasos:
- Si vis[i] es igual a 0, establezca el valor de d[i] como 1+a.segundo y vis[i] como 1 y coloque el par {i, d[i]} en la cola de pares q [].
- Inicialice un gráfico vectorial 2-D [][] con N número de filas para almacenar los vértices conectados desde cada vértice.
- Iterar sobre el rango [0, M] usando la variable i y realizar los siguientes pasos:
- Introduzca el valor de b-1 en el gráfico vectorial [][] en la fila a-1.
- Introduzca el valor de a-1 en el gráfico vectorial [][] en la fila b-1.
- Inicialice los vectores p[] y d[] de tamaño N para realizar un seguimiento de los Nodes principales y la longitud de las rutas.
- Llame a la función dist(graph, d, p, N) para encontrar la longitud del camino más corto.
- Inicializa un vector de distancias[] para almacenar la longitud de todos los caminos posibles.
- Introduzca el valor de d[N-1] en el vector distancias[].
- Inicialice un vector edge[] para obtener todos los bordes a lo largo de la ruta más corta.
- Llame a la función obtener_aristas(N-1, aristas, p) para encontrar todas las aristas a lo largo del camino más corto.
- Iterar sobre el rango [0, edge.size()-1] usando la variable i y realizar los siguientes pasos:
- Llame a la función dist_helper(graph, d, edge[i], edge[i+1], N) para encontrar todos los bordes a lo largo del camino más corto.
- Introduzca el valor de d[N-1] en el vector distancias[].
- Ordene las distancias vectoriales [] en orden ascendente.
- Si el tamaño del vector distancias[] es mayor que 1, devuelva el valor distancias[1]-distancias[0]; de lo contrario, devuelva 0 como respuesta.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to get all the edges in
// the shortest path
void get_edges(int s, vector<int>& edges, vector<int> p)
{
if (s == -1)
return;
get_edges(p[s], edges, p);
edges.push_back(s);
}
// Calculate the shortest distance
// after removing an edge between
// v1 and v2
void dist_helper(vector<vector<int> > graph, vector<int>& d,
int v1, int v2, int n)
{
// Vector to mark the nodes visited
vector<int> v(n, 0);
// For BFS
queue<pair<int, int> > q;
q.push(make_pair(0, 0));
v[0] = 1;
// Iterate over the range
while (!q.empty()) {
auto a = q.front();
q.pop();
for (int i : graph[a.first]) {
if ((i == v1 && a.first == v2)
|| (i == v2 && a.first == v1))
continue;
if (v[i] == 0) {
d[i] = 1 + a.second;
v[i] = 1;
q.push(make_pair(i, d[i]));
}
}
}
}
// Calculates the shortest distances and
// maintain a parent array
void dist(vector<vector<int> > graph, vector<int>& d,
vector<int>& p, int n)
{
// Vector to mark the nodes visited
vector<int> v(n, 0);
// For BFS
queue<pair<int, int> > q;
q.push(make_pair(0, 0));
v[0] = 1;
// Iterate over the range
while (!q.empty()) {
auto a = q.front();
q.pop();
for (int i : graph[a.first]) {
if (v[i] == 0) {
p[i] = a.first;
d[i] = 1 + a.second;
v[i] = 1;
q.push(make_pair(i, d[i]));
}
}
}
}
// Function to find the difference between the
// shortest and second shortest path
void findDifference(int n, int m, int arr[][2])
{
// Initializing and constructing the graph
vector<vector<int> > graph(n, vector<int>());
for (int i = 0; i < m; i++) {
int a, b;
a = arr[i][0];
b = arr[i][1];
graph[a - 1].push_back(b - 1);
graph[b - 1].push_back(a - 1);
}
// Initializing the arrays
vector<int> p(n, -1);
vector<int> d(n, 1e9);
// Calculate the shortest path
dist(graph, d, p, n);
// Vector to store the lengths
// of possible paths
vector<int> distances;
distances.push_back(d[n - 1]);
vector<int> edges;
// Get all the edges along the shortest path
get_edges(n - 1, edges, p);
// Iterate over the range
for (int i = 0; i + 1 < edges.size(); i++) {
// Calculate shortest distance after
// removing the edge
dist_helper(graph, d, edges[i], edges[i + 1], n);
distances.push_back(d[n - 1]);
}
// Sort the paths in ascending order
sort(distances.begin(), distances.end());
if (distances.size() == 1)
cout << 0 << endl;
else
cout << distances[1] - distances[0] << endl;
}
// Driver Code
int main()
{
int n, m;
n = 6;
m = 8;
int arr[m][2]
= { { 1, 2 }, { 1, 3 },
{ 2, 6 }, { 2, 3 },
{ 2, 4 }, { 3, 4 },
{ 3, 5 }, { 4, 6 } };
findDifference(n, m, arr);
return 0;
}
Python3
# Python3 program for the above approach edges, d, p = [], [], [] # Function to get all the edges in # the shortest path def get_edges(s): global edges, d, p if s == -1: return get_edges(p[s]) edges.append(s) # Calculate the shortest distance # after removing an edge between # v1 and v2 def dist_helper(graph, v1, v2, n): global edges, d, p # Vector to mark the nodes visited v = [0]*(n) # For BFS q = [] q.append([0, 0]) v[0] = 1 # Iterate over the range while len(q) > 0: a = q[0] q.pop(0) for i in graph[a[0]]: if (i == v1 and a[0] == v2) or (i == v2 and a[0] == v1): continue if v[i] == 0: d[i] = 1 + a[1] v[i] = 1 q.append([i, d[i]]) # Calculates the shortest distances and # maintain a parent array def dist(graph, n): global edges, d, p # Vector to mark the nodes visited v = [0]*(n) # For BFS q = [] q.append([0, 0]) v[0] = 1 # Iterate over the range while len(q) > 0: a = q[0] q.pop(0) for i in graph[a[0]]: if v[i] == 0: p[i] = a[0] d[i] = 1 + a[1] v[i] = 1 q.append([i, d[i]]) # Function to find the difference between the # shortest and second shortest path def findDifference(n, m, arr): global edges, d, p # Initializing and constructing the graph graph = [] for i in range(n): graph.append([]) for i in range(m): a = arr[i][0] b = arr[i][1] graph[a - 1].append(b - 1) graph[b - 1].append(a - 1) # Initializing the arrays p = [-1]*(n) d = [1e9]*(n) # Calculate the shortest path dist(graph, n) # Vector to store the lengths # of possible paths distances = [] distances.append(d[n - 1]) edges = [] # Get all the edges along the shortest path get_edges(n - 1) # Iterate over the range i = 0 while i + 1 < len(edges): # Calculate shortest distance after # removing the edge dist_helper(graph, edges[i], edges[i + 1], n) distances.append(d[n - 1]) i+=1 # Sort the paths in ascending order distances.sort() if len(distances) == 1: print(0) else: print(distances[1] - distances[0]) n = 6; m = 8; arr = [ [ 1, 2 ], [ 1, 3 ], [ 2, 6 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ], [ 3, 5 ], [ 4, 6 ] ] findDifference(n, m, arr) # This code is contributed by suresh07.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
static List<int> edges = new List<int>();
static List<int> d = new List<int>();
static List<int> p = new List<int>();
// Function to get all the edges in
// the shortest path
static void get_edges(int s)
{
if (s == -1)
return;
get_edges(p[s]);
edges.Add(s);
}
// Calculate the shortest distance
// after removing an edge between
// v1 and v2
static void dist_helper(List<List<int>> graph, int v1, int v2, int n)
{
// Vector to mark the nodes visited
List<int> v = new List<int>();
for(int i = 0; i < n; i++)
{
v.Add(0);
}
// For BFS
List<Tuple<int,int>> q = new List<Tuple<int,int>>();
q.Add(new Tuple<int,int>(0, 0));
v[0] = 1;
// Iterate over the range
while (q.Count > 0) {
Tuple<int,int> a = q[0];
q.RemoveAt(0);
for (int i = 0; i < graph[a.Item1].Count; i++) {
if ((graph[a.Item1][i] == v1 && a.Item1 == v2)
|| (graph[a.Item1][i] == v2 && a.Item1 == v1))
continue;
if (v[graph[a.Item1][i]] == 0) {
d[graph[a.Item1][i]] = 1 + a.Item2;
v[graph[a.Item1][i]] = 1;
q.Add(new Tuple<int,int>(graph[a.Item1][i], d[graph[a.Item1][i]]));
}
}
}
}
// Calculates the shortest distances and
// maintain a parent array
static void dist(List<List<int>> graph, int n)
{
// Vector to mark the nodes visited
List<int> v = new List<int>();
for(int i = 0; i < n; i++)
{
v.Add(0);
}
// For BFS
List<Tuple<int,int>> q = new List<Tuple<int,int>>();
q.Add(new Tuple<int,int>(0, 0));
v[0] = 1;
// Iterate over the range
while (q.Count > 0) {
Tuple<int,int> a = q[0];
q.RemoveAt(0);
for (int i = 0; i < graph[a.Item1].Count; i++) {
if (v[graph[a.Item1][i]] == 0) {
p[graph[a.Item1][i]] = a.Item1;
d[graph[a.Item1][i]] = 1 + a.Item2;
v[graph[a.Item1][i]] = 1;
q.Add(new Tuple<int,int>(graph[a.Item1][i], d[graph[a.Item1][i]]));
}
}
}
}
// Function to find the difference between the
// shortest and second shortest path
static void findDifference(int n, int m, int[,] arr)
{
// Initializing and constructing the graph
List<List<int>> graph = new List<List<int>>();
for(int i = 0; i < n; i++)
{
graph.Add(new List<int>());
}
for (int i = 0; i < m; i++) {
int a, b;
a = arr[i,0];
b = arr[i,1];
graph[a - 1].Add(b - 1);
graph[b - 1].Add(a - 1);
}
// Initializing the arrays
for(int i = 0; i < n; i++)
{
p.Add(-1);
d.Add(1000000000);
}
// Calculate the shortest path
dist(graph, n);
// Vector to store the lengths
// of possible paths
List<int> distances = new List<int>();
distances.Add(d[n - 1]);
// Get all the edges along the shortest path
get_edges(n - 1);
// Iterate over the range
for (int i = 0; i + 1 < edges.Count; i++) {
// Calculate shortest distance after
// removing the edge
dist_helper(graph, edges[i], edges[i + 1], n);
distances.Add(d[n - 1]);
}
// Sort the paths in ascending order
distances.Sort();
if (distances.Count == 1)
{
Console.WriteLine(0);
}
else
{
Console.WriteLine((distances[1] - distances[0]));
}
}
// Driver code
static void Main() {
int n, m;
n = 6;
m = 8;
int[,] arr
= { { 1, 2 }, { 1, 3 },
{ 2, 6 }, { 2, 3 },
{ 2, 4 }, { 3, 4 },
{ 3, 5 }, { 4, 6 } };
findDifference(n, m, arr);
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// Javascript program for the above approach
let edges = [], d = [], p = [];
// Function to get all the edges in
// the shortest path
function get_edges(s)
{
if (s == -1)
return;
get_edges(p[s]);
edges.push(s);
}
// Calculate the shortest distance
// after removing an edge between
// v1 and v2
function dist_helper(graph, v1, v2, n)
{
// Vector to mark the nodes visited
let v = [];
for(let i = 0; i < n; i++)
{
v.push(0);
}
// For BFS
let q = [];
q.push([0, 0]);
v[0] = 1;
// Iterate over the range
while (q.length > 0) {
let a = q[0];
q.shift();
for (let i = 0; i < graph[a[0]].length; i++) {
if ((graph[a[0]][i] == v1 && a[0] == v2)
|| (graph[a[0]][i] == v2 && a[0] == v1))
continue;
if (v[graph[a[0]][i]] == 0) {
d[graph[a[0]][i]] = 1 + a[1];
v[graph[a[0]][i]] = 1;
q.push([graph[a[0]][i], d[graph[a[0]][i]]]);
}
}
}
}
// Calculates the shortest distances and
// maintain a parent array
function dist(graph, n)
{
// Vector to mark the nodes visited
let v = [];
for(let i = 0; i < n; i++)
{
v.push(0);
}
// For BFS
let q = [];
q.push([0, 0]);
v[0] = 1;
// Iterate over the range
while (q.length > 0) {
let a = q[0];
q.shift();
for (let i = 0; i < graph[a[0]].length; i++) {
if (v[graph[a[0]][i]] == 0) {
p[graph[a[0]][i]] = a[0];
d[graph[a[0]][i]] = 1 + a[1];
v[graph[a[0]][i]] = 1;
q.push([graph[a[0]][i], d[graph[a[0]][i]]]);
}
}
}
}
// Function to find the difference between the
// shortest and second shortest path
function findDifference(n, m, arr)
{
// Initializing and constructing the graph
let graph = [];
for(let i = 0; i < n; i++)
{
graph.push([]);
}
for (let i = 0; i < m; i++) {
let a, b;
a = arr[i][0];
b = arr[i][1];
graph[a - 1].push(b - 1);
graph[b - 1].push(a - 1);
}
// Initializing the arrays
for(let i = 0; i < n; i++)
{
p.push(-1);
d.push(1e9);
}
// Calculate the shortest path
dist(graph, n);
// Vector to store the lengths
// of possible paths
let distances = [];
distances.push(d[n - 1]);
// Get all the edges along the shortest path
get_edges(n - 1);
// Iterate over the range
for (let i = 0; i + 1 < edges.length; i++) {
// Calculate shortest distance after
// removing the edge
dist_helper(graph, edges[i], edges[i + 1], n);
distances.push(d[n - 1]);
}
// Sort the paths in ascending order
distances.sort(function(a, b){return a - b});
if (distances.length == 1)
{
document.write(0 + "</br>");
}
else
{
document.write((distances[1] - distances[0]) + "</br>");
}
}
let n, m;
n = 6;
m = 8;
let arr
= [ [ 1, 2 ], [ 1, 3 ],
[ 2, 6 ], [ 2, 3 ],
[ 2, 4 ], [ 3, 4 ],
[ 3, 5 ], [ 4, 6 ] ];
findDifference(n, m, arr);
// This code is contributed by rameshtravel07.
</script>
Producción
1
Complejidad temporal: O(N*M)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por parthagarwal1962000 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA