Temas
Listas Simplemente (LSE) y Doblemente enlazadas (LDE)
- Estructura y Diseño de una LSE.
- Operaciones Insertar, Eliminar,Buscar en LSE.
- Estructura y Diseño de una LDE.
- Operaciones Insertar, Eliminar, Buscar en LDE.
- Listas Circular y operaciones.
- Análisis de complejidad Computacional.
Árboles Binarios
- Operaciones de inserción, eliminación y Búsqueda.
- Otras Operaciones en árboles binarios.
- Análisis de complejidad computacional.
Árboles Binarios Equilibrados
- Árboles AVL y operaciones de inserción, eliminación y Búsqueda.
- Árboles Red Black y operaciones de inserción, eliminación y Búsqueda.
- Segment Tree e Interval Tree.
- Análisis de complejidad computacional.
Matrices poco Densas
- Matrices poco densas Estáticas.
- Matrices poco densas Dinámicas.
- Optimización en eficiencia de Matrices Esparzas.
- Aplicaciones.
Tablas Hash
- Funciones de Dispersión.
- Densidad de Empaquetamiento.
- Operaciones de Inserción, Eliminación y Búsqueda.
- Análisis de complejidad computacional.
Estructuras de Datos en Grafos
Rutas más cortas
Algortimos sobre Grafos
- Árboles de Expansión Mínima ( Kruscall , Prim).
- Componentes Fuertemente conexos.
- Orden Topológico.
- Flujos Máximos y Mínimos.
- Coloreado de Grafos.
Árboles multicamino
Algoritmo de Dijkstra
Algoritmo de Dijkstra. También llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.
Historia
Fue creado y publicado por el Dr. Edsger W. Dijkstra, un científico Neerlandés brillante en ciencias de la computación e ingeniería de software.
En 1959, publicó un artículo de tres páginas titulado: "A note on two problems in connexion with graphs", lo cual se traduce a español como "Una nota sobre dos problemas relacionados con grafos." En este artículo explicó su nuevo algoritmo.
En una entrevista, Dijkstra cito: ¿Cuál es el camino más corto para viajar desde Rotterdam a Groningen? Es el algoritmo para el camino más corto, el cual diseñé en aproximadamente 20 minutos. Una mañana estaba comprando en Amsterdam con mi joven prometida, y cansados, nos sentamos en una terraza de un café para beber una taza de café y estaba pensando cómo podría hacerlo, y luego diseñé el algoritmo para el camino más corto. Como acabo de mencionar, fue un invento de 20 minutos. De hecho, fue publicado en 1959, tres años más tarde. La publicación sigue siendo bastante buena. Una de las razones de por qué es tan buena es que la diseñé casi sin lápiz ni papel. Sin lápiz ni papel no tienes otra opción más que evitar todas las complejidades que se puedes evitar. Con el tiempo, ese algoritmo se convirtió, para mi sorpresa, en una de las piedras angulares de mi fama
Aspectos básicos del algoritmo de Dijkstra
- El algoritmo de Dijkstra básicamente inicia en el nodo que escojas (el nodo de origen) y analiza el grafo para encontrar el camino más corto entre ese nodo y todos los otros nodos en el grafo.
- El algoritmo mantiene un registro de la distancia conocida más corta desde el nodo de origen hasta cada nodo y actualiza el valor si encuentra un camino más corto.
Una vez que el algoritmo ha encontrado el camino más corto entre el nodo de origen y otro nodo, ese nodo se marca como "visitado" y se agrega al camino.
El proceso continúa hasta que todos los nodos en el grafo han sido añadidos al camino. De esta forma, tenemos un camino que conecta al nodo de origen con todos los otros nodos siguiendo el camino más corto posible para llegar a cada uno de ellos.
Requisitos
El algoritmo de Dijkstra solo puede aplicarse a grafos con arcos cuyos valores o pesos son positivos. Esto se debe a que durante es proceso, los valores de los arcos deben ser sumados para encontrar el camino más corto.
Si existe un valor negativo en el grafo, el algoritmo no funcionará correctamente. Una vez que el nodo se marca como "visitado", el camino actual hacia ese nodo se marca como el camino más corto para alcanzar ese nodo pero los valores negativos pueden cambiar esto si el valor total puede ser reducido luego de este paso.
Pasos del algoritmo de Dijkstra
* Sea V un conjunto de vértices de un grafo.
* Sea C una matriz de costos de las aristas del grafo, donde en C[u,v] se almacena el costo de la arista entre u y v.
* Sea S un conjunto que contendrá los vértices para los cuales ya se tiene determinado el camino mínimo.
* Sea D un arreglo unidimensional tal que D[v] es el costo del camino mínimo del vértice origen al vértice v.
* Sea P un arreglo unidimensional tal que P[v] es el vértice predecesor de v en el camino mínimo que se tiene construido.
* Sea vinicial el vértice origen. Recordar que el Algoritmo Dijkstra determina los caminos mínimos que existen partiendo de un vértice origen al resto de los vértices.
Implementacion del Algoritmo de Dijkstra en C++
#include < iostream>
#include < queue>
#include < vector>
#define MAXV 100 // Maxima cantidad de vertices.
#define oo 0x3f3f3f3f // Nuestro valor infinito.
using namespace std;
struct Edge
{
int node; // El nodo destino de la arista.
int cost; // El costo de la arista.
Edge(int _node, int _cost) : node(_node), cost(_cost) {} // Constructor parametrizado.
Edge() : node(-1), cost(-1) {} // Constructor por defecto.
};
struct Graph
{
vector< Edge> G[MAXV]; // Lista de adyacencias.
int V; // Cantidad de vertices.
int E; // Cantidad de aristas.
};
struct State
{
int node; // El nodo actual.
int cost; // El costo del camino.
State(int _node, int _cost) : node(_node), cost(_cost) {} // Constructor parametrizado.
bool operator <(const State &b) const // Sobrecarga del operador de prioridad <.
{
return cost > b.cost;
}
};
int algoritmo(const int begin, const int end, const Graph graph)
{
priority_queue< State> pq; // La cola de prioridad.
vector< int> Dist(graph.V, oo); // La distancia hacia todos los vertices. Inicialmente para cada vertice su valor es infinito.
vector< bool> mark(graph.V, false); // Este arreglo nos permitira determinar los nodos procesados.
Dist[begin] = 0; // Valor inicial del vertice de partida.
pq.push(State(begin, 0)); // Agregamos el primer elemento, que no es mas que el vertice de partida.
while(!pq.empty()) // Mientras existan vertices por procesar.
{
State st = pq.top(); pq.pop(); // Se desencola el elemento minimo.
mark[st.node] = true; // Se marca el nodo como visitado.
if (st.node == end)
return st.cost; // Retornamos el valor del camino, hemos llegado al vertice destino.
int T = (int)graph.G[st.node].size();
for(int i = 0; i < T; ++i) // Se recorren las adyacencias de "a".
{
// Si no ha sido procesado el vertice "vi" y la distancia hacia "vi" es menor a la distancia
// en Dist entonces hemos encontrado un camino mas corto a "vi".
if (!mark[graph.G[st.node][i].node] && ((Dist[st.node] + graph.G[st.node][i].cost) < Dist[graph.G[st.node][i].node]))
{
Dist[graph.G[st.node][i].node] = st.cost + graph.G[st.node][i].cost;
pq.push(State(graph.G[st.node][i].node, st.cost + graph.G[st.node][i].cost));
}
}
}
return -1; // Si no se puede llegar al destino, retornar -1.
}
struct Programa
{
int V, E;
int comienzo, fin;
void definirGrafo(Graph& graph)
{
cout << "Ingrese Cantidad de Vertices: " << endl;
cin >> V;
cout << "Ingrese Cantidad de Aristas: " << endl;
cin >> E;
graph.V = V;
graph.E = E;
}
void cargarGrafo(Graph & graph)
{
for (int i = 0; i < E; ++i)
{
int Origen, Destino, Peso;
cout << "Ingrese Origen: " << endl;
cin >> Origen;
cout << "Ingrese Destino: " << endl;
cin >> Destino;
cout << "Ingrese Peso de la Arista: " << endl;
cin >> Peso;
// Insertamos la arista dos veces, ya que nuestro grafo es un grafo no dirigido.
graph.G[Origen].push_back(Edge(Destino, Peso));
graph.G[Destino].push_back(Edge(Origen, Peso));
}
}
void Dijkstra(Graph graph)
{
cout << "Ingrese Vertice Inicial: " << endl;
cin >> comienzo;
cout << "Ingrese Vertice Final: " << endl;
cin >> fin;
int n = algoritmo(comienzo, fin, graph);
cout << "Longitud del Camino mas Corto: " << n << endl;
}
};
int main()
{
bool out=false;
char salir;
Programa programa; //TAD
Graph graph; // Grafo.
cout << "Algoritmo de Dijkstra en C++" << endl;
while (!out)
{
programa.definirGrafo(graph); //Se define cantidad de vertices y cantidad de aristas del grafo
programa.cargarGrafo(graph); //Se cargan las aristas del Grafo
programa.Dijkstra(graph); //Se aplica el algoritmo de Dijkstra
//Desea Salir?
cout << "Salir? (S/N)" << endl;
cin >> salir;
if (salir == 'S')
{
out = true;
}
}
}
Link de apoyo