Costo mínimo usando Dijkstra modificando el costo de un borde

Dado un gráfico ponderado no dirigido de N Nodes y M aristas en forma de tupla, digamos {X, Y, Z} tal que hay una arista con costo Z entre X e Y. Se supone que debemos calcular el costo mínimo de recorrido desde el Node 1 a N. Sin embargo, podemos realizar una operación antes del recorrido de modo que podamos reducir el costo de cualquier borde, digamos, C a C / 2 (división entera) . 

Ejemplos: 

Entrada: N = 3, M = 4, Bordes = {{1, 2, 3}, {2, 3, 1}, {1, 3, 7}, {2, 1, 5}} 
Salida: 2 
Explicación: 
 

El costo mínimo desde el Node de origen 1 hasta el Node de destino N es = 3/2 + 1 = 1 + 1 = 2.
Entrada: N = 3, M = 3, Bordes = {{2, 3, 1}, {1, 3, 7}, {2, 1, 5}} 
Salida: 2 
Explicación: 
 

El costo mínimo desde el Node de origen 1 hasta el Node de destino N es = 7/2 = 3. 
 

Enfoque: La idea es considerar cada borde a modificar y tratar de minimizar el costo total al reducir su costo. La idea principal es dividir la ruta entre el Node 1 y N en la ruta desde 1 hasta cualquier vértice u , es decir, ruta (1 a u) y desde el Node N a cualquier vértice v , es decir, ruta (n a v) para todo u y v tales que u a v forman una arista . Podemos calcular fácilmente la distancia desde cualquier Node, digamos, fuente a todos los demás Nodes en el gráfico aplicando el algoritmo de ruta más corta de fuente única, algoritmo de Dijkstra. En este problema estaríamos aplicando elAlgoritmo de Dijkstra dos veces eligiendo fuentes como 1 y N por separado y almacenando el costo para llegar a cada Node en la array dist_from_source[] y dist_from_dest[] respectivamente. 
Después de haber calculado estas dos arrays, podemos calcular fácilmente el costo asociado después de modificar cada borde. Consideremos una arista de u a v y dejemos que el costo asociado sea c. Si intentamos modificar este borde, podemos calcular el costo mínimo de 1 a N como dist_from_source[u] + dist_from_dest[v] + c/2 . Haciendo esto para todos los bordes y minimizándolo, podemos obtener el costo mínimo para viajar desde la fuente 1 hasta el destino N. 
 

1. Realice un algoritmo de Dijkstra para encontrar la ruta más corta de fuente única para todos los vértices desde el Node 1 y guárdelo en una array como dist_from_source[] .
2. Realice un algoritmo de Dijkstra para encontrar la ruta más corta de fuente única para todos los vértices desde el Node N y guárdelo en una array como dist_from_dest[] .
3. Declare una variable minCost y asígnela a un número muy grande inicialmente.
4. Atraviese todos los bordes dados [u, v, c] y redúzcalos como la fórmula discutida anteriormente y actualice la variable minCost como:
    

minCost = min(minCost, dist_from_source[u] + c/2 + dist_from_dest[v]) 
donde, 
c es el costo del borde actual, 
dist_from_source[u] es el costo de la ruta desde el Node 1 hasta u 
dist_from_source[v] es el costo de camino del Node N a v 
 

1. Repita este proceso para todos los bordes y actualice correspondientemente la variable minCost .
    
2. Imprime el valor de minCost después del paso anterior.

A continuación se muestra la implementación del enfoque anterior:
 

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
 
// Function for Dijkstra Algorithm to
// find single source shortest path
void dijkstra(int source, int n,
              vector<pair<int,
                          int> >
                  adj[],
              vector<int>& dist)
{
    // Resize dist[] to N and assign
    // any large value to it
    dist.resize(n, INF);
 
    // Initialise distance of source
    // node as 0
    dist = 0;
 
    // Using min-heap priority_queue
    // for sorting wrt edges_cost
    priority_queue<pair<int, int>,
                   vector<pair<int,
                               int> >,
                   greater<pair<int,
                                int> > >
        pq;
 
    // Push the current dist
    // and source to pq
    pq.push({ dist, source });
 
    // Until priority queue is empty
    while (!pq.empty()) {
 
        // Store the cost of linked
        // node to edges
        int u = pq.top().second;
        // int d = pq.top().first;
 
        // Pop the top node
        pq.pop();
 
        // Iterate over edges
        for (auto& edge : adj[u]) {
 
            // Find the starting and
            // ending vertex of edge
            int v = edge.first;
            int w = edge.second;
 
            // Update the distance of
            // node v to minimum of
            // dist[u] + w if it is
            // minimum
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({ dist[v], v });
            }
        }
    }
}
 
// Function to find the minimum cost
// between node 1 to node n
void minCostPath(
    vector<pair<int, pair<int, int> > >& edges,
    int n, int M)
{
 
    // To create Adjacency List
    vector<pair<int, int> > adj[100005];
 
    // Iterate over edges
    for (int i = 0; i < M; i++) {
 
        // Get source, destination and
        // edges of edges[i]
        int x = edges[i].first;
        int y = edges[i].second.first;
        int z = edges[i].second.second;
 
        // Create Adjacency List
        adj[x].push_back({ y, z });
        adj[y].push_back({ x, z });
    }
 
    // To store the cost from node 1
    // and node N
    vector<int> dist_from_source;
    vector<int> dist_from_dest;
 
    // Find the cost of travel between
    // source(1) to any vertex
    dijkstra(1, n + 1, adj, dist_from_source);
 
    // Find the cost of travel between
    // destination(n) to any vertex
    dijkstra(n, n + 1, adj, dist_from_dest);
 
    // Initialise the minimum cost
    int min_cost = dist_from_source[n];
 
    // Traverse the edges
    for (auto& it : edges) {
 
        // Get the edges
        int u = it.first;
        int v = it.second.first;
        int c = it.second.second;
 
        // Find the current cost from
        // node 1 to u and node u to v
        // and node v to N with only
        // current edge cost reduced
        // to half
        int cur_cost = dist_from_source[u]
                       + c / 2
                       + dist_from_dest[v];
 
        // Update the min_cost
        min_cost = min(min_cost, cur_cost);
    }
 
    // Print the minimum cost
    cout << min_cost << '\n';
}
 
// Driver Code
int main()
{
    // Give Nodes and Edges
    int N = 3;
    int M = 3;
 
    // Given Edges with cost
    vector<pair<int, pair<int, int> > > edges;
 
    edges.push_back({ 2, { 3, 1 } });
    edges.push_back({ 1, { 3, 7 } });
    edges.push_back({ 2, { 1, 5 } });
 
    // Function Call
    minCostPath(edges, N, M);
    return 0;
}

<script>
 
// Javascript program for the above approach
 
// Function for Dijkstra Algorithm to
// find single source shortest path
function dijkstra(source, n, adj, dist)
{
 
    // Resize dist[] to N and assign
    // any large value to it
    dist = Array(n).fill(1000000000);
 
    // Initialise distance of source
    // node as 0
    dist = 0;
 
    // Using min-heap priority_queue
    // for sorting wrt edges_cost
    var pq = [];
 
    // Push the current dist
    // and source to pq
    pq.push([dist, source]);
 
    // Until priority queue is empty
    while (pq.length!=0) {
 
        // Store the cost of linked
        // node to edges
        var u = pq[pq.length-1][1];
        // int d = pq.top()[0];
 
        // Pop the top node
        pq.pop();
 
        // Iterate over edges
        for (var edge of adj[u]) {
 
            // Find the starting and
            // ending vertex of edge
            var v = edge[0];
            var w = edge[1];
 
            // Update the distance of
            // node v to minimum of
            // dist[u] + w if it is
            // minimum
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push([dist[v], v ]);
            }
        }
        pq.sort();
    }
    return dist;
}
 
// Function to find the minimum cost
// between node 1 to node n
function minCostPath(edges, n, M)
{
 
    // To create Adjacency List
    var adj = Array.from(Array(100005), ()=>new Array());
 
    // Iterate over edges
    for (var i = 0; i < M; i++) {
 
        // Get source, destination and
        // edges of edges[i]
        var x = edges[i][0];
        var y = edges[i][1][0];
        var z = edges[i][1][1];
 
        // Create Adjacency List
        adj[x].push([y, z ]);
        adj[y].push([x, z ]);
    }
 
    // To store the cost from node 1
    // and node N
    var dist_from_source = [];
    var dist_from_dest = [];
 
    // Find the cost of travel between
    // source(1) to any vertex
    dist_from_source = dijkstra(1, n + 1, adj, dist_from_source);
 
    // Find the cost of travel between
    // destination(n) to any vertex
    dist_from_dest = dijkstra(n, n + 1, adj, dist_from_dest);
 
    // Initialise the minimum cost
    var min_cost = dist_from_source[n];
 
    // Traverse the edges
    for (var it of edges) {
 
        // Get the edges
        var u = it[0];
        var v = it[1][0];
        var c = it[1][1];
 
        // Find the current cost from
        // node 1 to u and node u to v
        // and node v to N with only
        // current edge cost reduced
        // to half
        var cur_cost = dist_from_source[u]
                       + parseInt(c / 2)
                       + dist_from_dest[v];
 
        // Update the min_cost
        min_cost = Math.min(min_cost, cur_cost);
    }
 
    // Print the minimum cost
    document.write( min_cost + "<br>");
}
 
// Driver Code
// Give Nodes and Edges
var N = 3;
var M = 3;
 
// Given Edges with cost
var edges = [];
edges.push([2, [3, 1]]);
edges.push([1, [3, 7 ]]);
edges.push([2, [1, 5 ]]);
 
// Function Call
minCostPath(edges, N, M);
 
// This code is contributed by noob2000.
 
</script>

# Python3 program for the above approach
import heapq as hq
 
INF = 1e9
 
# Function for Dijkstra Algorithm to
# find single source shortest path
def dijkstra(source, n, adj, dist):
    # Initialise distance of source
    # node as 0
    dist = 0
 
    # Using min-heap priority_queue
    # for sorting wrt edges_cost
    pq = []
 
    # Push the current dist
    # and source to pq
    hq.heappush(pq, (dist, source))
 
    # Until priority queue is empty
    while pq:
 
        # Store the cost of linked
        # node to edges
        d, u = hq.heappop(pq)
 
        # Iterate over edges
        for v,w in adj[u]:
 
            # Update the distance of
            # node v to minimum of
            # dist[u] + w if it is
            # minimum
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                hq.heappush(pq, (dist[v], v))
 
 
# Function to find the minimum cost
# between node 1 to node n
def minCostPath(edges, n, M):
 
    # To create Adjacency List
    adj = [[]for _ in range(100005)]
 
    # Iterate over edges
    for i in range(M):
 
        # Get source, destination and
        # edges of edges[i]
        x = edges[i][0]
        y = edges[i][1][0]
        z = edges[i][1][1]
 
        # Create Adjacency List
        adj[x].append((y, z))
        adj[y].append((x, z))
 
    # To store the cost from node 1
    # and node N
    dist_from_source = [INF] * (n+1)
    dist_from_dest = [INF] * (n+1)
 
    # Find the cost of travel between
    # source(1) to any vertex
    dijkstra(1, n + 1, adj, dist_from_source)
 
    # Find the cost of travel between
    # destination(n) to any vertex
    dijkstra(n, n + 1, adj, dist_from_dest)
 
    # Initialise the minimum cost
    min_cost = dist_from_source[n]
 
    # Traverse the edges
    for it in edges:
 
        # Get the edges
        u = it[0]
        v = it[1][0]
        c = it[1][1]
 
        # Find the current cost from
        # node 1 to u and node u to v
        # and node v to N with only
        # current edge cost reduced
        # to half
        cur_cost = dist_from_source[u] + c // 2 + dist_from_dest[v]
 
        # Update the min_cost
        min_cost = min(min_cost, cur_cost)
 
    # Print minimum cost
    print(min_cost)
 
 
# Driver Code
if __name__ == "__main__":
    # Give Nodes and Edges
    N = 3
    M = 3
 
    # Given Edges with cost
    edges = []
 
    edges.append((2, (3, 1)))
    edges.append((1, (3, 7)))
    edges.append((2, (1, 5)))
 
    # Function Call
    minCostPath(edges, N, M)

3

Complejidad temporal: O(M log N), donde N es el número de Nodes y M es el número de aristas. 
Espacio Auxiliar: O(N), donde N es el número de Nodes.