1.- Obtener las componenetes fuertemente conexas para el grafo de la figura.

3.- Corra el algoritmo de Dijkstra sobre el grafo dirigido de la figura, primero usando el vertice s como fuente y luego usando el vertice y como fuente. Muestre los valores de d, p y S despues del lazo while.

4.- Invente un ejemplo simple de un grafo dirigido con arcos de peso negativo para el cual el algoritmo de Dijkstra produzca una respuesta incorrecta.

5.- Suponga que cambiamos la condición del while en el algoritmo de Dijkstra a lo siguiente: while (|Q| > 1)
Esto causa que el loop while se ejecute |V|-1 veces en lugar de |V|.  ¿Se obtiene así un algoritmo correcto?

6.- Sea un grafo G=(V,E) sobre el cual cada arco (u,v) en E tiene asociado un valor r(u,v), el cual es un número real en el rango 0<= r(u,v) <=1 que representa la confiabilidad de un canal de comunicación desde el vertice u al v. Interpretamos r(u,v) como la probabilidad que el canal desde u a v no fallará, y suponemos que estas probabilidades son independientes. Proponda un algoritmo eficiente para encontrar el camino más confiable entre dos vértices dados.

7.- Para el grafo de la figura corra el algoritmo Bellman-Ford usando el vértice "y" como fuente u origen. "Relaje" los arcos en orden alfabético en cada pasada (Por ejemplo (u,v) va primero que (u,x) y luego de considerar los arcos con origen en u, debo cosiderar los arcos on origen en v.  Luego de cada pasada por todos los arcos muestre los arreglos d y p. Finalmente, cambie el peso del arco (y,v) a 4 y corra el algoritmo nuevamente usando z como fuente.