algorithm - porque - gráfico-Camino más corto con peso de vértice
metodo bellman ford (2)
El peso del vértice se puede eliminar cortando cada vértice a en dos vértices a1 y a2 con un borde de a1 a a2 con el peso de a.
Creo que tienes razón para la adaptación del algoritmo de dijkstra.
Aquí hay un impuesto especial:
En ciertos problemas de gráficos, los vértices pueden tener pesos en lugar de, o además de los pesos de los bordes. Sea Cv el costo del vértice v, y C (x, y) el costo del borde (x, y). Este problema tiene que ver con encontrar la ruta más barata entre los vértices a y b en un gráfico G. El costo de una ruta es la suma de los costos de los bordes y vértices encontrados en la ruta.
(a) Suponga que cada borde en el gráfico tiene un peso de cero (mientras que los no bordes tienen un costo de). Suponga que Cv = 1 para todos los vértices 1≤v≤n (es decir, todos los vértices tienen el mismo costo) . Ofrezca un algoritmo eficiente para encontrar la ruta más económica de aab y su complejidad de tiempo.
(b) Ahora suponga que los costos de vértice no son constantes (pero son todos positivos) y que los costos de borde se mantienen como se indicó anteriormente. Ofrezca un algoritmo eficiente para encontrar la ruta más económica de aab y su complejidad de tiempo.
(c) Ahora suponga que los costos de borde y vértice no son constantes (pero todos son positivos). Ofrezca un algoritmo eficiente para encontrar la ruta más económica de aab y su complejidad de tiempo.
Aquí está mi respuesta:
(a) usar BFS normal;
(b) Use el algoritmo de dijkstra, pero reemplace el peso con el peso del vértice;
(do)
También usa el algoritmo de dijkstra.
Si solo consideramos el peso del borde, entonces para la parte clave del algoritmo de dijkstra, tenemos:
if (distance[y] > distance[v]+weight) {
distance[y] = distance[v]+weight; // weight is between v and y
}
Ahora, considerando el peso del vértice, tenemos:
if (distance[y] > distance[v] + weight + vertexWeight[y]) {
distance[y] = distance[v] + weight + vertexWeight[y]; // weight is between v and y
}
Estoy en lo cierto?
Supongo que mi respuesta a (c) es demasiado simple, ¿verdad?
Usted está en el camino correcto y la solución es muy simple.
Tanto en B, C, reduzca el problema a dijkstra normal, que no asume ningún peso en los vértices.
Para esto, deberá definir w'':E->R , una nueva función de peso para los bordes.
w''(u,v) = w(u,v) + vertex_weight(v)
en (b) w(u,v) = 0 (o const), y la solución es robusta para encajar (c) también!
La idea subyacente es usar un borde que le cueste el peso del borde y el costo de alcanzar el vértice objetivo. El costo de la fuente ya se pagó, por lo que no tiene en cuenta 1 .
¡Reducir un problema, en lugar de cambiar un algoritmo suele ser mucho más fácil de usar, probar y analizar!
(1) En esta solución, "pierde" el peso de la fuente, por lo que el camino más corto de s a t será: dijkstra(s,t,w'') + vertex_weight(s)_ [donde dijkstra(s,t,w'') es la distancia desde s hasta t usando w''