Aufgabe zu Dijkstra Algorithm Networking:
To debug network architectures, it may be necessary to understand which router was used to establish a connection to another computer in the network. For this purpose there are tools such as the program tracert (short for "trace route" or "trace route"), which calculates a list of all routers used on the way to the target computer. For this purpose, characteristics of the common network protocols are used which are not described in detail here. Instead, let's assume an abstract network with the following protocol: If you want to send a packet to a target computer, it is guaranteed to arrive at the target computer on the shortest path. You will receive an answer to each of your packages
- how long your parcel was on its way to the target computer in milliseconds,
- from which computers the target computer can be addressed directly (ie in one step) and
- How many milliseconds a packet needs from these computers to the target computer.
We also assume that a computer that can directly reach another does not have to be directly reachable by this one, so that the communication paths are not necessarily bidirectional. We also assume that the latency from one computer to the next is consistently greater than 0 throughout the entire execution and that the network is contiguous.
1. Describe an algorithm which, given a target computer \( t \) in the network, outputs a complete shortest path for your packet to the target computer t. Also enter a corresponding pseudocode in which you can use the function sendPackage \( (x) \) to send a packet to computer \( x \) and receive the response as a tuple \( (d, Y, T) \), where \( d \) is the required time in milliseconds until the target computer is, \( Y \) are the computers that can reach \( x \) directly and \( T \) are the transmission times of packets from computers in \( Y \) to \( x \).
2. Transfers in the network are usually much slower than operations on the CPU. The total runtime is therefore likely to be dominated by the transmission time in the network. Enter a change to the protocol or more specifically to sendePaket \( (x) \), with which the number of transmission times required in the network could be reduced. The improvement does not have to have any influence on the asymptotic running time.
