Dado un gráfico dirigido ponderado con N vértices y M aristas, un origen src y un destino objetivo , la tarea es encontrar el camino monótono más corto (monótonamente creciente o decreciente) desde el origen hasta el destino. Salida -1 si no es posible una ruta monotónica.
Nota: Todos los pesos son no negativos
Ejemplos:
Entrada: N = 6, M = 9, src = 1, objetivo = 2
bordes = {{1, 3, 1.1}, {1, 5, 2}, {1, 6, 3.3}, {2, 5, 2.7 },
{3, 4, 2}, {3, 5, 1,1}, {4, 2, 2,3}, {5, 6, 2,4}, {6, 2, 3}}
Gráfico para el primer ejemplo
Salida: 5.4
Explicación: Hay tres caminos monótonos en el gráfico
que se originan en el vértice 1, que son 1 – 6 – 2 porque es estrictamente creciente,
y 1 – 3 – 4 – 2 y 1 – 5 – 6 – 2 porque ambos son estrictamente decrecientes.
El más corto de estos caminos es 1 – 3 – 4 – 2,
que tiene una suma de pesos igual a 1,1 + 2 + 2,3 = 5,4,
por lo que la salida es 5,4.Entrada: N = 5, M = 5, src = 1, objetivo = 5
bordes = {{1, 2, 2.3}, {1, 3, 3.1}, {2, 3, 3.7}, {3, 4, 1.9 }, {4, 5, 2.1}}
Gráfico para el segundo ejemplo
Salida: -1
Explicación: No existe una ruta monotónica desde el vértice 1 al vértice 5.
Acercarse:
Ejecute el algoritmo de Dijkstra dos veces: uno para aumentar las rutas más cortas y otro para disminuir las rutas más cortas, y tome la ruta más corta de los dos resultados.
- Ejecute el algoritmo de Dijkstra dos veces para caminos crecientes y decrecientes.
- Al hacer Dijkstra para disminuir los caminos más cortos:
- Solo actualice la ruta más corta a un vértice v desde el vértice u si el peso del borde de u a v es menor que el borde en la ruta más corta dirigida hacia u .
- De manera similar para los caminos más cortos crecientes:
- Solo actualice el camino más corto a un vértice v desde u , si el borde de u a v es mayor que el borde en el camino más corto dirigido hacia u .
- Al hacer Dijkstra para disminuir los caminos más cortos:
- Si aún no se ha alcanzado el vértice de destino, entonces no existe una ruta más corta válida.
- Si ambos pases de Dijkstra en rutas más cortas crecientes y decrecientes dan como resultado rutas no válidas, entonces devuelva -1 .
A continuación se muestra la implementación del enfoque anterior.
Java
import java.io.*;
import java.util.*;
// Finds the monotonic shortest path
// using Djikstra's algorithm
class Main {
public static void main(String[] args)
{
int N = 6;
int M = 9;
// Create an array of vertices
Vertex[] vertices = new Vertex[N + 1];
// Create instances of each vertex from 1 to N
for (int i = 1; i <= N; i++)
vertices[i] = new Vertex(i);
vertices[1].adjList.add(3);
vertices[1].adjWeights.add(1.1);
vertices[1].adjList.add(5);
vertices[1].adjWeights.add(2.0);
vertices[1].adjList.add(6);
vertices[1].adjWeights.add(3.3);
vertices[2].adjList.add(5);
vertices[2].adjWeights.add(2.7);
vertices[3].adjList.add(4);
vertices[3].adjWeights.add(2.0);
vertices[3].adjList.add(5);
vertices[3].adjWeights.add(1.1);
vertices[4].adjList.add(2);
vertices[4].adjWeights.add(2.3);
vertices[5].adjList.add(6);
vertices[5].adjWeights.add(2.4);
vertices[6].adjList.add(2);
vertices[6].adjWeights.add(3.0);
// Source and destination vertices
int src = 1;
int target = 2;
System.out.println(
shortestPath(vertices, N, src, target));
}
public static double shortestPath(Vertex vertices[],
int N, int source,
int destination)
{
// Stores distance from source and edge
// on the shortest path from source
double[] distTo = new double[N + 1];
double[] edgeTo = new double[N + 1];
// Set initial distance from source
// to the highest value
for (int i = 1; i <= N; i++)
distTo[i] = Double.MAX_VALUE;
// Monotonic decreasing pass of dijkstras
distTo = 0.0;
edgeTo = Double.MAX_VALUE;
PriorityQueue<Vertex> pq
= new PriorityQueue<Vertex>(
new Comparator<Vertex>() {
public int compare(Vertex a, Vertex b)
{
return Double.compare(distTo[a.id],
distTo[b.id]);
}
});
// Add the initial source vertex
// into the priority queue
pq.add(vertices);
while (!pq.isEmpty()) {
// Take the vertex with the closest
// current distance from source
Vertex closest = pq.remove();
for (int i = 0; i < closest.adjList.size();
i++) {
// Checks if the edges are decreasing and
// whether the current directed edge will
// create a shorter path
if (closest.adjWeights.get(i)
< edgeTo[closest.id]
&& distTo[closest.id]
+ closest.adjWeights.get(i)
< distTo[closest.adjList.get(
i)]) {
edgeTo[closest.adjList.get(i)]
= closest.adjWeights.get(i);
distTo[closest.adjList.get(i)]
= closest.adjWeights.get(i)
+ distTo[closest.id];
pq.add(
vertices[closest.adjList.get(i)]);
}
}
}
// Store the result of the first pass of dijkstras
double firstPass = distTo[destination];
// Monotonic increasing pass of dijkstras
for (int i = 1; i <= N; i++)
distTo[i] = Double.MAX_VALUE;
distTo = 0.0;
edgeTo = 0.0;
// Add the initial source vertex
// into the priority queue
pq.add(vertices);
while (!pq.isEmpty()) {
// Take the vertex with the closest current
// distance from source
Vertex closest = pq.remove();
for (int i = 0; i < closest.adjList.size();
i++) {
// Checks if the edges are increasing and
// whether the current directed edge will
// create a shorter path
if (closest.adjWeights.get(i)
> edgeTo[closest.id]
&& distTo[closest.id]
+ closest.adjWeights.get(i)
< distTo[closest.adjList.get(
i)]) {
edgeTo[closest.adjList.get(i)]
= closest.adjWeights.get(i);
distTo[closest.adjList.get(i)]
= closest.adjWeights.get(i)
+ distTo[closest.id];
pq.add(
vertices[closest.adjList.get(i)]);
}
}
}
// Store the result of the second pass of Dijkstras
double secondPass = distTo[destination];
if (firstPass == Double.MAX_VALUE
&& secondPass == Double.MAX_VALUE)
return -1;
return Math.min(firstPass, secondPass);
}
}
// Represents a vertex in the graph
// id stores the vertex number of the vertex instance
// adjList stores the id's of adjacent vertices
// adjWeights stores the weights of adjacent vertices with
// the same indexing as adjList
class Vertex {
int id;
ArrayList<Integer> adjList;
ArrayList<Double> adjWeights;
// A constructor which accepts
// the id of the vertex
public Vertex(int num)
{
id = num;
adjList = new ArrayList<Integer>();
adjWeights = new ArrayList<Double>();
}
}
5.4
Complejidad temporal: O(N log(N) + M)
Espacio auxiliar: O(N)