Module: Algoritmo de Dijkstra


Problem

1/14

Dijkstra: El comienzo (C++)

Theory Click to read/hide

Dado un gráfico ponderado dirigido o no dirigido con n vértices y m aristas. Los pesos de todos los bordes no son negativos. Se especifica algún vértice inicial. Debe encontrar las longitudes de las rutas más cortas desde el vértice s hasta todos los demás vértices, y también proporcionar una forma de imprimir las rutas más cortas.
 
Este problema se denomina "problema de ruta más corta de fuente única" (problema de rutas más cortas de fuente única).

Realiza las mismas tareas que 1-K BFS, pero sin tener en cuenta K. Además, como 1-K BFS, no maneja adecuadamente los bordes negativos

Algoritmo:
El propio algoritmo de Dijkstra consta de N iteraciones. En la siguiente iteración, el vértice V  con la distancia más pequeña a él de entre los vértices aún no marcados, este vértice se marca y se producen relajaciones de los vértices vecinos a partir de él.


 el comportamiento asintótico final del algoritmo es: O(n2+ m)

Problem

Se le proporciona un gráfico ponderado dirigido. Encuentra la distancia más corta de un vértice dado a otro.
 
Entrada
La primera línea contiene tres números: N, S y F (1≤ N≤ 100, 1≤ S, F≤ N), donde N – número de vértices del gráfico, S – vértice inicial y F – final. En las próximas N líneas, ingrese N números cada uno, sin exceder 100, – ponderar la matriz de adyacencia del gráfico, donde -1 significa que no hay borde entre los vértices y cualquier número no negativo – la presencia de una arista de peso dado. Los ceros se escriben en la diagonal principal de la matriz.
 
Salida
Se requiere mostrar la distancia deseada o -1 si no hay camino entre los vértices especificados.

Ejemplos

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
# Entrada Salida
1
3 2 1
0 1 1
4 0 1
2 1 0
 3
Write the program below 
#include<iostream>
 
using namespace std;
 
int main()
{
    const int N1 = 110;
    int N, S, F, g[N1][N1], i, j, mini, d[N1];
    bool used[N1];
   
    cin >> N >> S >> F;
   
    fill(used, used + N, false);
   
    fill(d, d + N, 10000000);
   
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
            cin >> g[i][j];
    }
   
    d[S - 1] = 0;
   
    for (i = 0; i < N; i++)
    {
        mini = -1;
       
        for (j = 0; j < N; j++)
        {
            if (!used[j] && (mini == -1 || d[j] < d[mini]))
                mini = j;
        }
       
        used[mini] = true; 
    if (d[F - 1] == 10000000)
        cout << "-1";
    else
        cout << d[F - 1];
}

     

Program check result

To check the solution of the problem, you need to register or log in!