Certaines variantes du problème de plus court chemin ne cherchent pas à minimsier la somme des arêtes, mais plutôt à optimiser une valeur extrême le long d’un chemin — comme le poids maximal ou minimal d’une arête. Ces cas exigent une révision de la fonction de relaxation standard.

Problème : Distacne maximale minimisée (Frogger)

Ici, l’objectif est de trouver un chemin entre deux nœuds tel que le poids de l’arête la plus lourde sur ce chemin soit aussi petit que possible. La relaxation classique est remplacée par :

dist[v] = min(dist[v], max(dist[u], poids(u,v)))

Exemple d'implémentation :

#include <iostream>
#include <queue>
#include <cmath>
#include <cstring>
using namespace std;

const float INF = 1e9;
int N;

struct Point {
    int id;
    float px, py;
    float max_edge;
    bool operator<(const Point& other) const {
        return max_edge > other.max_edge;
    }
};

Point points[1005];
bool visited[1005];

void solve_frogger() {
    memset(visited, 0, sizeof(visited));
    for (int i = 1; i <= N; ++i) {
        cin >> points[i].px >> points[i].py;
        points[i].id = i;
        points[i].max_edge = INF;
    }
    points[1].max_edge = 0.0f;

    priority_queue<Point> pq;
    pq.push(points[1]);

    while (!pq.empty()) {
        Point cur = pq.top(); pq.pop();
        if (visited[cur.id]) continue;
        visited[cur.id] = true;

        for (int j = 1; j <= N; ++j) {
            if (j == cur.id) continue;
            float dist = sqrt(pow(points[j].px - cur.px, 2) + pow(points[j].py - cur.py, 2));
            float candidate = max(cur.max_edge, dist);
            if (candidate < points[j].max_edge) {
                points[j].max_edge = candidate;
                pq.push(points[j]);
            }
        }
    }
}

int main() {
    int case_num = 1;
    while (cin >> N, N != 0) {
        solve_frogger();
        cout << "Scenario #" << case_num << endl;
        cout << "Frog Distance = ";
        printf("%.3f\n\n", points[2].max_edge);
        case_num++;
    }
    return 0;
}

Problème : Capacité minimael maximisée (Heavy Transportation)

Dans ce cas, on cherche le chemin dont l’arête la plus faible a le poids le plus élevé possible — utile pour modéliser des capacités de transport. La relaxation devient :

cap[v] = max(cap[v], min(cap[u], weight(u,v)))

Implémentation adaptée :

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int INF = 1e9;
int node_count, edge_count;

struct Vertex {
    int id;
    int min_capacity;
    bool operator<(const Vertex& other) const {
        return min_capacity < other.min_capacity;
    }
};

Vertex vertices[1005];
vector<pair<int, int>> graph[1005];
bool processed[1005];

void solve_transport() {
    memset(processed, 0, sizeof(processed));
    for (int i = 1; i <= node_count; ++i) {
        vertices[i].id = i;
        vertices[i].min_capacity = 0;
    }
    vertices[1].min_capacity = INF;

    priority_queue<Vertex> pq;
    pq.push(vertices[1]);

    while (!pq.empty()) {
        Vertex current = pq.top(); pq.pop();
        if (processed[current.id]) continue;
        processed[current.id] = true;

        for (auto& edge : graph[current.id]) {
            int neighbor = edge.first;
            int capacity = edge.second;
            int new_cap = min(current.min_capacity, capacity);
            if (new_cap > vertices[neighbor].min_capacity) {
                vertices[neighbor].min_capacity = new_cap;
                pq.push(vertices[neighbor]);
            }
        }
    }
}

int main() {
    int scenarios;
    cin >> scenarios;
    for (int idx = 1; idx <= scenarios; ++idx) {
        cin >> node_count >> edge_count;
        for (int i = 1; i <= node_count; ++i)
            graph[i].clear();

        for (int e = 0; e < edge_count; ++e) {
            int u, v, w;
            cin >> u >> v >> w;
            graph[u].push_back({v, w});
            graph[v].push_back({u, w});
        }

        solve_transport();
        cout << "Scenario #" << idx << ":\n" << vertices[node_count].min_capacity << endl << endl;
    }
    return 0;
}