¿Qué es un modelo ponderado?
2. El problema más común resuelto con gráficos ponderados es el problema del camino más corto (pps).
3. El árbol de expansión mínimo de un gráfico ponderado contiene todos los vértices y los bordes necesarios que los conectan, y los pesos de estos bordes son los más pequeños.
4. El algoritmo de cola de prioridad se puede utilizar para encontrar el árbol de expansión mínimo del gráfico ponderado.
5. Método para resolver el árbol de expansión mínimo de un gráfico ponderado no dirigido.
1) Encuentre todos los bordes desde el último vértice hasta otros vértices que no pueden estar en el conjunto de árboles y use estos bordes como una cola de prioridad.
2) Encuentra la arista de menor peso y colócala junto con los vértices a los que llega dentro del conjunto de árboles.
3) Repita los pasos anteriores hasta que todos los vértices estén en el conjunto de árboles.
6. El problema del camino más corto de los gráficos ponderados se puede resolver mediante el algoritmo de Dijkstra. El algoritmo se basa en la representación matricial de adyacencia del gráfico. No sólo puede encontrar el camino más corto entre dos puntos cualesquiera, sino que también puede encontrar el camino más corto desde un punto específico hasta todos los demás vértices.
La idea del algoritmo de Dijkstra;
Tome como ejemplo encontrar una ruta con el costo más bajo de una ciudad a otra (suponiendo que los costos de todas las rutas no pueden ser directamente derivado, pero sólo se puede conocer directamente el coste de viajar a ciudades vecinas).
1) Envíe un agente a una nueva ciudad a la vez, utilice la nueva información proporcionada por el agente para modificar y mejorar la lista de tarifas y retenga la tarifa más baja desde el punto de origen hasta una determinada ciudad en la mesa.
2) Despachar continuamente agentes a una nueva ciudad, siempre que la ruta desde el punto de origen hasta esa ciudad tenga el menor coste.
Dibujar
7. A veces, para ver si una ruta es factible, es necesario crear una tabla de conexiones. En un gráfico ponderado, se utiliza una tabla para dar el costo mínimo entre dos vértices cualesquiera, que pueden estar conectados por varias aristas. Este problema se denomina problema del camino más corto entre cada par de vértices. El algoritmo de Warshall (que se detalla en el sello) puede crear rápidamente dicha tabla de unión. Un enfoque similar en gráficos ponderados se llama algoritmo de Freud.
La diferencia entre el algoritmo Floyd y el algoritmo Warshall. Cuando se encuentra una ruta de dos segmentos en el algoritmo de Warshall, simplemente inserta 1 en la tabla. En el algoritmo de Floyd, es necesario sumar los pesos en ambos extremos y luego insertar su suma.