graphs

Question 1

what are we given in shortest path problems

Answer 1

1-A weighted, directed graph G = (V, E)
2-Weight function w: E  R mapping edges to real valued weights.

Question 2

what is The weight w(p) of path

Answer 2

is the sum of the weights of its constituent edges

Question 3

whats the shortest path from u to v

Answer 3

any path p between u and v with minimum weight

Question 4

what is Single-source shortest path problem

Answer 4

its where we need to find shortest path from given source s∈V to each distanation in v∈V

Question 5

talk about shortest path problems and edges whose weights are negative

Answer 5

there is two ways that negative edges can go or form in the graph:

1-(acceptable)If the **graph G (V,E) contains no negative-weight cycles reachable from the source s, then for all v ∈ V **, the shortest-path weight remains well defined, even if it has a negative value.
.
2-(not-acceptable)If the graph contains a negative-weight cycle reachable from s, however, shortest-path weights are not well defined. No path from s to a vertex on the cycle can be the shortest

Question 6

what is negative cycle

Answer 6

Negative cycle: directed cycle whose sum of edges costs is negative.

Question 7

Can a shortest path contain a cycle?

Answer 7

bc we assume it has no cycles
thus
-It can not contain a positive-weight cycle.
-since we will be removing the cycle, it produces a new path with the same source and destination vertices and a lower path weight.

Question 8

number of edges in single shortest path

Answer 8

|V|-1 edges even if there is cycle
bc:removing the cycle, it produces a new path with the same source and destination vertices and a lower path weight.

Question 9

diffrences between dijkstra and bellman-ford algorthims

Answer 9

dikstrea: Assumes that all edge weights in the input graph are nonnegative

bellman:Allows negative-weight edges in the input graph and produce a correct answer as long as no negative-weight cycles are reachable from the source.

Question 10

what is relaxation what do we need to intioalize before doing it

Answer 10

The process of relaxing an edge (u,v) consists of testing whether we can improve the shortest path to v found so far by going through u and, if so, updating v.d and v.  .

we need before doing to intialize all vertxis by:For each vertex v∈V, we maintain an attribute v.d, which is an upper bound on the weight of a shortest path from source s to v. We call v.d a shortest-path estimate

Question 11

lise all

Question 12

T or F: A relaxation step always decrease the value of the shortest-path estimate v.d and update v’s predecessor attribute v. .

Answer 12

F
A relaxation step may and may not decrease the value of the shortest-path estimate v.d and update v’s predecessor attribute v. .

Question 13

write intilize-single-source method and what is it for

Answer 13

is to preapare the for relax method with:
1-intilaize all vertixes vlaues(that costed to reach them)
.
2-intinlize all predecosr for given vertics

Question 14

write the code for relax method

Answer 14

Question 15

a propertiy in dikestra algorthim

Answer 15

Dijkstra’s algorithm maintains a set S of vertices whose final shortest-path weights from the source s have already been determined

Question 16

write dikjstra algorthim and all its components

Answer 16

Question 17

Analysis of Dijkstra’s Algorithm if we bulid Q as array

Answer 17

Question 18

Analysis of Dijkstra’s Algorithm if we bulid Q as MinHeap

Answer 18

Question 19

solve

Answer 19

Question 20

what can effect the running time of dijkstra

Answer 20

The running time depends on how we implement the min-priority queue Q.
Array
Min-heap

Question 21

bellman-ford proprties

Answer 21

1-Allows negative-weight edges.
2-Returns TRUE if no negative-weight cycles reachable from s, FALSE otherwise.
3-The algorithm makes |V|-1 passes.
4- slower than Dijkstra’s algorithm
5-Each pass relaxes all edges of the graph.
6-Computes d[v] and [v] for all v ∈ V .

Question 22

quickest single shortest path algorthim

Answer 22

dijkstra algorthim

Question 23

signficunt propertiy in bell-man algorthim

Answer 23

it relaxes all edges of the graph with each pass.

Question 24

write psudocode for bellaman-ford algorthim

Answer 24

Question 25

slove

Answer 25

Question 26

Analysis of Bellman-ford Algorithm

Answer 26